# The number of non-isomorphic spanning trees in K4

K4 has 16 spanning trees. I believe there are two non-isomorphic spanning trees in K4. Is this because half of the spanning trees have the sequence (1,2,2,1) as the degrees of their vertices, while the other half have (1,3,3,1)? Or is there some other reason why just two of the spanning tree graphs of K4 are non-isomorphic?

-
In case you'd like to finish your question, there's an edit link underneath it. – joriki Oct 25 '12 at 23:02
You might find this useful: austinmohr.com/work/trees. – Austin Mohr Oct 25 '12 at 23:08

You're essentially asking for the number of non-isomorphic trees on $4$ vertices. Here they are:

We can verify that we have not omitted any non-isomorphic trees as follows.

The total number of labelled trees on $n$ vertices is $n^{n-2}$, called Cayley's Formula. When $n=4$, there are $4^2=16$ labelled trees.

The number of labelled graphs isomorphic to a graph $G$ is given by $$\frac{n!}{|\mathrm{Aut}(G)|}$$ where $n$ is the number of vertices of the graph, and $\mathrm{Aut}(G)$ is the automorphism group of the graph. This is a consequence of the Orbit-Stabiliser Theorem. In the above two cases, the automorphism groups have size $6$ (and is isomorphic to $S_3$) and $2$, respectively.

So the $16$ labelled $4$-vertex trees partition into $24/6=4$ trees isomorphic to the tree on the left and $24/2=12$ trees isomorphic to the tree on the right. Since $16=4+12$, we have accounted for all isomorphism classes of trees.

(Note: more than half of the labelled $4$-vertex trees are isomorphic to the graph on the right.)

-

## protected by Community♦Apr 30 '15 at 5:40

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).