TAOCP 2.3.4.2 Exercise 20
Let $A$ be the incidence matrix of exercise 18.
Section 2.3.4.2: Oriented Trees
Exercise 20. [**] $$M21$$ If $G$ is an undirected graph on $n+1$ vertices $V_0,\ldots,V_n$, let $B$ be the $n\times n$ matrix defined as follows for $1\le i,j\le n$:
$$ b_{ij}= \begin{cases} t, & \text{if } i=j \text{ and there are } t \text{ edges touching } V_j;\ -1, & \text{if } i\ne j \text{ and } V_i \text{ is adjacent to } V_j;\ 0, & \text{otherwise.} \end{cases} $$
For example, if $G$ is the graph of Fig. 29 on page 363, with $(V_0,V_1,V_2,V_3,V_4)=(A,B,C,D,E)$, we find that
$$ B= \begin{pmatrix} 3 & 0 & -1 & -1\ 0 & 2 & -1 & 0\ -1 & -1 & 3 & -1\ -1 & 0 & -1 & 2 \end{pmatrix}. $$
Show that the number of free subtrees of $G$ is $\det B$. [Hint: Use exercise 18 or 19.]
Verified: yes
Solve time: 1m13s
Let $A$ be the incidence matrix of exercise 18. For an undirected graph, assign an arbitrary orientation to each edge and form $A$. The matrix $A^T A$ has entries
$$ (A^T A){ij}=\sum_k a{ki}a_{kj}. $$
If $i=j$, each edge incident with $V_j$ contributes $1$ to the sum, hence
$$ (A^T A)_{jj}=t, $$
where $t$ is the number of edges touching $V_j$. If $i\ne j$, an edge joining $V_i$ and $V_j$ contributes $-1$, and all other edges contribute $0$; therefore
$$ (A^T A)_{ij}= \begin{cases} -1, & \text{if } V_i \text{ is adjacent to } V_j,\ 0, & \text{otherwise.} \end{cases} $$
Thus the matrix $B$ of the exercise is exactly $A_0^T A_0$, where $A_0$ is obtained from $A$ by deleting column $0$.
By exercise 18(b), the determinant of $A_0^T A_0$ is the number of free subtrees of $G$. Since $B=A_0^T A_0$, this number is
$$ \det B. $$
Hence the number of free subtrees of $G$ is $\boxed{\det B}$. ∎