Matrix Tree Theorem

Revision as of 11:26, 3 March 2022 by Arr0w (talk | contribs) (Created page with "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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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).$