Hello everyone!

With the semester almost halfway over I realized it was beyond time I did some cool math.

Today I’ll be walking you through a proof of Kirchhoff’s matrix-tree theorem. Which is *super* important in the world of graph theory and has seriously awesome implications for computer science- as it takes a potentially super-exponential problem and solves it in polynomial time!

So, what does Krichhoff’s theorem even state?

The number of nonidentical spanning trees of a graph G is equal to any cofactor of its Laplacian matrix.

Ah! That’s a lot of mathy words. Let’s take them one by one…

 

 

Now, this still looks scary, so let’s look at an example.

Okay! Now we are so close to what we need to calculate the total number of spanning trees of a graph G…we now know how to computer a cofactor, but we need to find the cofactor of a particular matrix, the Laplacian of a graph G.

Math is pesky in the sense that by defining one thing you may need to find the definition of another. In this case we need the degree matrix of a graph.

Now that we have that definition and the degree matrix for our recurring example on graph G, let’s calculate the Laplacian Matrix! All we need to do is subtract the adjacency matrix from the degree matrix.

Okay, awesome, let’s take this example one step further and calculate the cofactor of the laplacian matrix of graph G (or, via kirchhoff’s theroem, the number of unique spanning trees of G). Let’s take a step back and think about putting everything together mathematically.

The last thing we need to do is to find the cofactor of our Laplacian Matrix…which we do the exact same way we did above. Let i =j =1 (because any values for i and j will give the same result),

and we get three! This matches the number of spanning trees we originally drew out above. So, amazing, Kirchhoff’s theorem appears to be working correctly. However, we have yet to prove that Kirchhoff’s theorem holds for all graphs G.

Let’s prove a specific case of Kirchhoff’s theorem where i=j, just to make it easier on ourselves…

to understand why this fact is true case consider the permutation sum definition of a determinant,

since we’ve increased the (i,i)th entry, a_ii, to a_ii + 1. So we get the original determinant PLUS a sum over all permutations of [n] \{i}, avoiding the ith row and column, i.e. det(A[i]).

(if you don’t believe this permutation sum def’n is true I completely understand. some extra resources on this step here and here).

 

So within this new terminology G/e we now have to define what contracted means…(smoosh is a technical term)

The right figure represents i being contracted onto j .

At this point we’ve proved what we’ve set out to prove! how?

WOO! This is a powerful proof, since it allows us to calculate the total number of spanning trees in polynomial time. More on it’s applications soon!

Alright back to (real) work now. If anyone asks I was totally working on my research today.

 

Resources:

https://cp-algorithms.com/graph/kirchhoff-theorem.html

https://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.html

https://byjus.com/cofactor-formula/

https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem

https://people.orie.cornell.edu/dpw/orie6334/lecture8.pdf

https://mathworld.wolfram.com/MatrixTreeTheorem.html

https://math.stackexchange.com/questions/1665210/fact-regarding-kirchhoffs-theorem