12 ***Graphs and matrices***12.2 Laplacian Matrix 12.4 More properties of Adjacency Matrix

12.3 Spanning trees and Laplacian

We recall the famed Cauchy-Binet formula. For an $n\times m$ matrix $A$ and a $m\times n$ matrix $B$ with $n\leq m$ , we have that

det(AB)=\sum_{S\subset[m],|S|=n}det(A[[n]|S])det(B[S|[n]]),

where $A[T|S]$ refers to the matrix $A$ restricted to rows in $T$ and columns in $S$ . Let $W=V-\{1\}$ and we can apply the Cauchy-Binet formula to $L[W|W]$ . As $L=\partial_{1}\partial_{1}^{t}$ , we have that $L[W|W]=\partial_{1}[W|\overrightarrow{E}]\partial_{1}^{t}[\overrightarrow{E}|W]$ .

det(L[W|W])=\sum_{S\subset\overrightarrow{E}:|S|=n-1}det(\partial_{1}[W|S])det% (\partial_{1}^{t}[S|W])=\sum_{S\subset E:|S|=n-1}det(\partial_{1}[W|S])^{2},

where the last equality is due to the fact that $\partial_{1}[W|S]=\partial_{1}^{t}[S|W]$ . Since the sum of rows in $\partial_{1}[V|S]$ is $0$ , $r(\partial_{1}[W|S])=r(\partial_{1}[V|S])$ . Hence, if $G$ is not connected, then $r(\partial_{1}[W|\overrightarrow{E}])<n-1$ and $det(L[W|W])=0$ . Thus, if $|E|<n-1$ , the LHS and the RHS in the above equation are zero. Assume that $G$ is connected.

Fix $S\subset\overrightarrow{E}:|S|=n-1$ . Then $det(\partial_{1}[W|S])\neq 0$ iff $\partial_{1}[W|S]$ is non-singular iff $\partial_{1}[W|S]$ has full column rank iff $r(\partial_{1}[W|S])=r(\partial_{1}[V|S])=n-1$ iff $S$ is acyclic iff $S$ is a spanning tree in $G$ . Thus, we have that

det(L[W|W])=\sum_{S\subset\overrightarrow{E},\mbox{spanning tree}}det(\partial% _{1}[W|S])^{2}.

Suppose we show that $det(\partial_{1}[W|S])\in\{0,-1,+1\}$ , then we have that

det(L[W|W])=|\mbox{Spanning trees of $G$}|.

(12.2)

The following lemma completes the proof.

Lemma 12.11.

For $W\subset V,S\subset\overrightarrow{E}$ such that $|W|=|S|$ , we have that $det(\partial_{1}[W|S])\in\{0,-1,+1\}$ .

Proof.

We will prove by induction on $k=|W|=|S|$ . Let $B=\partial_{1}[W|S]$ . The case of $k=1$ is trivial as the entries are $0,-1,+1$ . Assume that the theorem holds for all $l<k$ for $k\geq 2$ .

If each column of $B$ has both a $+1$ and a $-1$ entry, then the sum of rows is $0$ and $detB=0$ . If there is a column of $0$ ’s in $B$ , then $detB=0$ again. Hence, there is a column with only a single non-zero entry in $B$ . Suppose this is the $(w,s)$ -th entry. Then, we have that $detB=B_{w,s}det(\partial_{1}[W-\{w\}|S-\{s\}])$ . By induction, the latter is $0,-1,+1$ and since $B_{w,s}=+1,-1$ , we obtain the desiered conclusion. ∎

Corollary 12.12.

Let $0=\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}$ be the eigenvalues of $L$ . Then the number of spanning trees of $G$ is $\frac{\prod_{i=2}^{n}\lambda_{i}}{n}$ .

Proof.

Let $S T$ be the number of spanning trees of $G$ .

n\times ST=\sum_{W\subset[n],|W|=n-1}det(L[W|W])=\sum_{W\subset[n],|W|=n-1}% \prod_{i\in W}\lambda_{i},

as the sum of $k$ the principal minors of a matrix is equal to the sum of products of $k$ eigenvalues. Since $\lambda_{1}=0$ , RHS is $\lambda_{2}\ldots\lambda_{n}$ . ∎

As an easy corollary, we can obtain Cayley’s formula by noting that

Theorem 12.13.

(Kirchoff’s matrix tree theorem) Let $W\subset[n]$ and $|W|=n-k$ . Then $det(L[W|W])$ is the number of spanning forests in $G$ with $k$ components and each of the elements of $W^{c}$ being in a distinct component.

Proof.

(Proof Sketch) Let $W^{c}=\{w_{1},\ldots,w_{k}\}$ . Again by Cauchy-Binet, we have that

det(L[W|W])=\sum_{S\subset E:|S|=n-k}det(\partial_{1}[W|S])^{2}

From Lemma 12.11, we know that $det(\partial_{1}[W|S])=0,-1,+1$ and hence it is enough to show that $\partial_{1}[W|S]$ is non-singular iff the edges of $S$ forms a forest with $k$ components with each $w_{i}$ in a distinct component.

Let the edges of $S$ forms a forest with $k$ components with each $w_{i}$ in a distinct component, say $D_{i}$ . Let the edges in the $i$ th component be $S_{i}$ . Set $W_{i}=D_{i}-w_{i}$ . We have that $\cup W_{i}=W$ and $\cup S_{i}=S$ . Thus $\partial_{1}[W|S]$ is a block matrix with blocks $\partial_{1}[W_{i}|S_{i}],i=1,\ldots,k$ . By the proof of Corollary 12.12, we have that $det(\partial_{1}[W_{i}|S_{i}])\in\{-1,+1\}$ as $(D_{i},S_{i})$ forms a trees and hence $det(\partial_{1}[W|S])\in\{-1,+1\}$

If $\partial_{1}[W|S]$ is non-singular, then the columns of $S$ in $\partial_{1}[[n]|S]$ are linearly independent and hence the edges in $S$ form a forest and they have $k$ components as $|S|=n-k$ . It remains to be shown that $w_{i}$ are in distinct $k$ components. Since $([n],S)$ forms a forest with $k$ components, $\partial_{1}[[n]|S]$ and so $\partial_{1}[W|S]$ has a block structure with $k$ blocks. If one of the blocks (say with rows $W_{i})$ doesn’t contain any $w_{i}$ , then $\partial_{1}[W_{i}|S]$ is singular and so will be $\partial_{1}[W|S]$ . This leads to a contradiction. ∎