Number of spanning trees of a graph (behind the formula)

Question

Given $G$ a subgraph of $K_n$ s.t. $G$ has $n$ vertices with adjacency matrix $A$;

why is $$\sum_{T \text{ spanning tree of }K_n}\prod_{(i,j)\in T}A_{i,j}$$ the number of spanning trees?

I can't get it.

Answer 1

I'm assuming this means you have a graph $G$ on $n$ vertices with adjacency matrix $A$, and you want to count the number of spanning trees of $G$.

Now, $G$ is a subgraph of $K_n$, and so any spanning tree of $G$ is certainly a spanning tree of $K_n$. But a spanning tree $T$ of $K_n$ is not necessarily a spanning tree of $G$. In particular, $T$ is not a spanning tree of $G$ if and only if $T$ includes an edge $(i,j)$ of $K_n$ that is not an edge of $G$. In this case, $A_{i,j}=0$. So a spanning tree $T$ of $K_n$ is a spanning tree of $G$ if and only if $\prod_{(i,j)\in T}A_{i,j}=1$.

So the number of spanning trees of $G$ is the sum over all trees $T$ of $K_n$ in which $\prod_{(i,j)\in T}A_{i,j}=1$, which is your formula.

Answer 2

It seems that $A$ is the adjacency matrix of the complete graph. So $A_{i,j}=1$ whenever $i \neq j$ and $A_{i,i}=0$.

So $$\sum_{T \text{ spanning tree of }K_n}\prod_{(i,j)\in T}A_{i,j}=\sum_{T \text{ spanning tree of }K_n}1$$ which is the number of spanning trees of $K_n$.

Note: this would still work if $K_n$ were replaced by an arbitrary graph $G$, and the sum was over spanning trees $T$ of $G$, since if $(i,j) \in T$ then $(i,j) \in G$.