An Example Using The Matrix-tree Theorem
We first construct the Laplacian matrix Q for the example kite graph G (see image at right):
![Q = \left[\begin{array}{rrrr}
3 & -1 & -1 & -1 \\
-1 & 2 & -1 & 0 \\
-1 & -1 & 3 & -1 \\
-1 & 0 & -1 & 2
\end{array}\right].](http://upload.wikimedia.org/math/8/0/f/80f9e224c68fc40c4b842eb9c01e6d4d.png)
We now construct a matrix Q* by deleting any row s and any column t (s and t not necessarily distinct) from Q. For this example, we will delete row 1 and column 1 to obtain
![Q^\ast =
\left[\begin{array}{rrr}
2 & -1 & 0 \\
-1 & 3 & -1 \\
0 & -1 & 2
\end{array}\right].](http://upload.wikimedia.org/math/8/9/a/89a0c8f57efd9a6f1f463e74020110ae.png)
Finally, we take the determinant of Q* to obtain t(G). t(G) is thus the (1,1) cofactor of Q. In this example t(G) is 8.
Read more about this topic: Kirchhoff's Theorem
Famous quotes containing the word theorem:
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)