Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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: – 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:

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|cite|improve this answer

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

Would you like to answer one of these unanswered questions instead?

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