Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

1 Answer 1

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

The two non-isomorphic trees on $4$ vertices

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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