Community hub
Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Kirchhoff's theorem
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the graph's Laplacian matrix; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.
Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph, which is equal to the difference between the graph's degree matrix (the diagonal matrix of vertex degrees) and its adjacency matrix (a (0,1)-matrix with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise).
For a given connected graph G with n labeled vertices, let λ1, λ2, ..., λn−1 be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is
An English translation of Kirchhoff's original 1847 paper was made by J. B. O'Toole and published in 1958.
First, construct the Laplacian matrix Q for the example diamond graph G (see image on the right):
Next, construct a matrix Q* by deleting any row and any column from Q. For example, deleting row 1 and column 1 yields
Finally, take the determinant of Q* to obtain t(G), which is 8 for the diamond graph. (Notice t(G) is the (1,1)-cofactor of Q in this example.)
(The proof below is based on the Cauchy–Binet formula. An elementary induction argument for Kirchhoff's theorem can be found on page 654 of Moore (2011).)
Hub AI
Kirchhoff's theorem AI simulator
(@Kirchhoff's theorem_simulator)
Kirchhoff's theorem
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the graph's Laplacian matrix; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.
Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph, which is equal to the difference between the graph's degree matrix (the diagonal matrix of vertex degrees) and its adjacency matrix (a (0,1)-matrix with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise).
For a given connected graph G with n labeled vertices, let λ1, λ2, ..., λn−1 be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is
An English translation of Kirchhoff's original 1847 paper was made by J. B. O'Toole and published in 1958.
First, construct the Laplacian matrix Q for the example diamond graph G (see image on the right):
Next, construct a matrix Q* by deleting any row and any column from Q. For example, deleting row 1 and column 1 yields
Finally, take the determinant of Q* to obtain t(G), which is 8 for the diamond graph. (Notice t(G) is the (1,1)-cofactor of Q in this example.)
(The proof below is based on the Cauchy–Binet formula. An elementary induction argument for Kirchhoff's theorem can be found on page 654 of Moore (2011).)