Suppose the graph is:
Find the number of spanning trees in the graph.
I used the matrix tree theorem and found the adjacency matrix to be:
$A = \begin{smallmatrix} 0&1&1&0\\ 1&0&1&1\\ 1&1&0&1\\ 0&1&1&0\\ \end{smallmatrix}$
and the degree matrix is $D = \begin{smallmatrix} 2&0&0&0\\ 0&3&0&0\\ 0&0&3&0\\ 0&0&0&2\\ \end{smallmatrix}$
Then
$D-A = \begin{smallmatrix} 2&-1&-1&0\\ -1&3&-1&-1\\ -1&-1&3&-1\\ 0&-1&-1&2\\ \end{smallmatrix}$
Finding the cofactor of this gives a matrix composed of just 8.
By the matrix tree theorem, then the number of spanning trees in the graph is 8.
However, Cayley's tree formula also says that there are $n^{n-2}$ distinct labeled trees of order n. Since we know that there are 4 vertices in the graph, then the spanning tree must also have 4 vertices. This gives $4^{4-2} = 16$ distinct labeled trees of order 4.
According to the answer to this question, the correct solution is 8. Why can I not use Cayley's tree formula to solve this?
Best Answer
Cayley's formula counts all labeled trees of order $n$. In your case, this includes trees that use the edge $\{1,4\}$, which is absent from the graph you posted.
(As for why the overcount is exactly a factor of $2$: with $6$ possible edges among the four vertices and $3$ edges in every tree on $4$ vertices, you should expect every possible edge to show up in exactly half the labeled trees, so exactly half of the possible labeled trees counted by Cayley's formula will contain the edge $1,4$.)