Editing Kirchhoff's theorem (section)

== Proof outline ==

(The proof below is based on the [[Cauchy–Binet formula]]. An elementary [[mathematical induction|induction]] argument for Kirchhoff's theorem can be found on page 654 of Moore (2011).<ref name="Moore 2011 p. 654 ">{{cite book | last=Moore | first=Cristopher | title=The nature of computation | publisher=Oxford University Press | publication-place=Oxford England New York | year=2011 | isbn=978-0-19-923321-2 | oclc=180753706 }}</ref>)

First notice that the Laplacian matrix has the property that the sum of its entries across any row and any column is 0. 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.

We proceed to show that the determinant of the minor ''M''<sub>11</sub> is the number of spanning trees. Let ''n'' be the number of vertices of the graph, and ''m'' the number of its edges. The incidence matrix ''E'' is an ''n''-by-''m'' matrix, which may be defined as follows: suppose that (''i'', ''j'') is the ''k''th edge of the graph, and that ''i'' < ''j''. Then ''E<sub>ik</sub>'' = 1, ''E<sub>jk</sub>'' = −1, and all other entries in column ''k'' are 0 (see [[oriented incidence matrix]] for understanding this modified incidence matrix ''E'').  For the preceding example (with ''n'' = 4 and ''m'' = 5):

:<math>E = \begin{bmatrix}
   1 &  1 &  0 &  0 &  0 \\
  -1 &  0 &  1 &  1 &  0 \\
   0 & -1 & -1 &  0 &  1 \\
   0 &  0 &  0 & -1 & -1 \\
\end{bmatrix}.</math>

Recall that the Laplacian ''L'' can be factored into the product of the [[incidence matrix]] and its [[transpose]], i.e., ''L'' = ''EE''<sup>T</sup>. Furthermore, let ''F'' be the matrix ''E'' with its first row deleted, so that ''FF''<sup>T</sup> = ''M''<sub>11</sub>.

Now the [[Cauchy–Binet formula]] allows us to write

:<math>\det\left(M_{11}\right) = \sum_S \det\left(F_S\right)\det\left(F_S^{\mathrm{T}}\right) = \sum_S \det\left(F_S\right)^2</math>

where ''S'' ranges across subsets of [''m''] of size ''n'' −&thinsp;1, and ''F<sub>S</sub>'' denotes the (''n'' −&thinsp;1)-by-(''n'' −&thinsp;1) matrix whose columns are those of ''F'' with index in ''S''. Then every ''S'' specifies ''n'' −&thinsp;1 edges of the original graph, and it can be shown that those edges induce a spanning tree if and only if the determinant of ''F<sub>S</sub>'' is +1 or −1, and that they do not induce a spanning tree if and only if the determinant is 0. This completes the proof.