Fact regarding Kirchhoff's Theorem

763 Views Asked by At

Question regarding Kirchhoff's Theorem:

If $ L(G)$ denotes the Laplacian of a graph $G$ then Kirchhoff's Theorem states that number of spanning trees in $G$ is equal to $(-1)^{i+j} \det L(i|j)$ where $L(i|j)$ is obtained by deleting the $i^{th}$ row and $j^{th}$ column.

But how does that give that number of spanning trees is equal to $\frac{1}{n}\{\lambda_1 \lambda_2...\lambda_{n-1}\}$ where $\lambda_i$ are non-zero eigen values of $L(G)$.

Please help me to understand the second result stated in bold

2

There are 2 best solutions below

7
On BEST ANSWER

An easy way to obtain this result from Kirchhoffs Theorem is the following (following "Biggs, Algebraic graph theory"):

Step 1 (Temperley 1964) For a graph $X$ with $n$ vertices and its Laplacian $L=L(X)$ it holds that $$ \tau(X) = n^{-2} \text{det}(J + L),$$ where $J$ is the matrix with all entries equal to $1$ and $\tau(X)$ is the number of spanning trees.

Proof: By the following two formulas $nJ = J^2$ and $LJ = JL = \textbf{0}$ we easily obtain $$(nI - J)(J+L)=nL.$$ Taking adjugates on both sides one gets $$\text{adj}(nI-J) \text{adj}(J+L) = \text{adj}(nL).$$ Now one uses that $nI-J = L(K_n)$, i.e. the Laplacian of the complete graph, hence $\text{adj}(nI-J)$ equals $n^{n-2}J$. Moreover using $\text{adj}(nL) = n^{n-1}\text{adj}(L)$ one obtains $$\text{adj}(J+L) J= n \tau(X) J.$$ Multiplying this equation by $(J + L)$ finally gives the result.

Step 2: $\tau(X) = n^{-1} \prod \lambda_i$ where $\lambda_1, \dots, \lambda_{n-1}$ are the non-zero eigenvalues of $L$.

Proof: $J$ and $L$, as it was used above commute. Hence they are simultaneously diagonalizable. Hence the eigenvalues of $J+L$ are just the sum of the corresponding eigenvalues of $J$ and $L$. As the eigenvalues of $J$ are $n, 0, 0, \dots, 0$ the eigenvalues of $J+L$ are $n, \lambda_1, \dots, \lambda_{n-1}$. Now since the determinant equals the product of eigenvalues, Step 1 settles the proof.

0
On

Your answer can be found at

https://saadquader.wordpress.com/2013/03/25/kirchhoffs-matrix-tree-theorem-for-counting-spanning-trees-proof/

or at:

www.math.ucsd.edu/~jverstra/264A-LECTUREJ.pdf