I am having trouble understanding Kirchhoff's Theorem.
The statement I want to prove is that if $\lambda_1,\lambda_2,...,\lambda _{n-1}$ are non-zero eigen values of $L(G)$ then
Number of Spanning Trees of $G$ is $t(G)=\frac{1}{n}\{\lambda_1,\lambda_2,...,\lambda _{n-1}\}=$
Any co-factor of the Laplacian Matrix $L(G)$
I am reading from Wikipedia Article of Kirchhoff's Theorem
Proof:
- First notice that the Laplacian has the property that the sum of its entries across any row and any column is 0.
2.Thus we can transform any minor into any other minor by adding rows and columns, switching them, and multiplying a row or a column by $−1$. Thus the cofactors are the same up to sign, and it can be verified that, in fact, they have the same sign$ \longrightarrow $ (How is this true)??
3.We proceed to show that the determinant of the minor $M_{11}$ counts the number of spanning trees. Let $n$ be the number of vertices of the graph, and $ m$ the number of its edges. Consider The incidence matrix $E$ which is an $n\times m$ matrix.
- $L = EE^T$.
5.let $F $ be the matrix $E$ with its first row deleted, so that $FF^T = M_{11}.$
6.Now the Cauchy-Binet formula allows us to write
$\det(M_{11}) = \sum_S \det(F_S)\det(F^T_S) = \sum_S \det(F_S)^2$ where $S$ ranges across subsets of $[m]$ of size $n − 1$, and $F_S$ denotes the $(n − 1)\times (n − 1)$ matrix whose columns are those of $F $ with index in $S$. Then every $S$ specifies $n − 1 $ edges of the original graph, and it can be shown that those edges induce a spanning tree iff the determinant of $F_S$ is $+1$ or $−1$, and that they do not induce a spanning tree iff the determinant is $0$
**I am unable to understand the points $2,5,6$ and how does that prove the theorem .Please help me to understand the points $2,5,6$ and help me to complete the theorem.