2
$\begingroup$

Suppose the graph is:

Graph

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Another way to phrase it is that Cayley's formula counts the number of spanning trees on the complete graph. :-) $\endgroup$ – ml0105 Feb 23 '16 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.