Editing Kirchhoff's theorem (section)

== An example using the matrix-tree theorem ==

[[Image:Graph with all its spanning trees.svg|thumb|The Matrix-Tree Theorem can be used to compute the number of labeled spanning trees of this graph.]]

First, construct the Laplacian matrix ''Q'' for the example [[diamond graph]] ''G'' (see image on the right):

: <math>Q = \left[\begin{array}{rrrr}
2 & -1 & -1 & 0 \\
-1 & 3 & -1 & -1 \\
-1 & -1 & 3 & -1 \\
0 & -1 & -1 & 2
\end{array}\right].</math>

Next, construct a matrix ''Q''<sup>*</sup> by deleting any row and any column from ''Q''.  For example, deleting row 1 and column 1 yields

: <math>Q^\ast = \left[\begin{array}{rrr}
3 & -1 & -1 \\
-1 & 3 & -1 \\
-1 & -1 & 2
\end{array}\right].</math>

Finally, take the determinant of ''Q''<sup>*</sup> to obtain ''t''(''G''), which is 8 for the diamond graph. (Notice ''t''(''G'') is the (1,1)-cofactor of ''Q'' in this example.)