Matrix Tree Theorem

The Matrix Tree Theorem is a theorem in Graph Theory that counts for the number of spanning trees of a connected graph. It was discovered by Gustav Kirchhoff, which is why the theorem is also called Kirchhoff's Matrix Tree Theorem or simply Kirchhoff's Theorem.

Statement

Let $G$ be a graph with the set of vertices $V=\{v_1,v_2,v_3,\ldots, v_n\}$ . We define its adjacency matrix $\mathcal{A}(G)$ as

$\mathcal{A}(G)_{i,j}=\begin{cases}1 & \text{if}~v_i\sim v_j\\ 0 & \text{if otherwise}.\end{cases}$

where $i$ is an arbitrary row in the matrix, $j$ is an arbitrary column, and $\sim$ denotes that two vertices are connected. Next, define the degree matrix as

$\mathcal{D}(G)=\begin{pmatrix} &\deg(v_1)&&&&\\ &&\deg(v_2)&&&\\ &&&\ddots&&\\ &&&&\deg(v_n)&\\ \end{pmatrix}.$

Using both the adjacency and degree matrix of $G$ , we define the Laplacian Matrix $\mathcal{L}(G)$ as

$\mathcal{L}(G)=\mathcal{D}(G)-\mathcal{A}(G)$ .

Lastly, let $\mathcal{L}''(G)$ denote the deletion of the $n$ th row and column of $\mathcal{L}(G)$ . Now we can state the theorem. Let $G$ be a connected graph with laplacian $\mathcal{L}(G)$ and let $\tau(G)$ be the number of spanning trees of $G$ . Then

$\det(\mathcal{L}''(G))=\tau(G).$

Page

Toolbox

Search

Matrix Tree Theorem

Statement