Show that there are exactly six non-isomorphic trees on six vertices. ("Introduction to Combinatorics" p.183)
The solutions were provided in the book. But why can we be sure that there are ONLY six non-isomorphic trees?
$\endgroup$2 Answers
$\begingroup$From Cayley's Tree Formula, we know there are precisely $6^4=1296$ labelled trees on $6$ vertices.
The $6$ non-isomorphic trees are listed below.
(These trees were generated as described in this answer.)
We also compute:
- the size of the automorphism group $|\mathrm{Aut}(G)|$ of the tree $G$ (I did this using brute force checking of all $6!$ permutations) and
- the number of labelled trees isomorphic to $G$, which is given by $\frac{6!}{|\mathrm{Aut}(G)|}$ by the Orbit-Stabiliser Theorem.
We see that $$6+120+360+90+360+360=1296=6^4$$ which matches Cayley's Tree Formula, so no tree is missing.
$\endgroup$ 4 $\begingroup$Brute force.
There is one tree (path) with all vertices of degree 2 or 1, two trees with one vertex of degree 3 and the others of degree 2 or 1 (branch at edge or middle), one tree each with vertices of degrees 4,5 all other degrees 2 or 1, degrees higher than 5 are impossible, one tree with 2 vertices of degree 3, and the degrees must sum to 10 (or $2(n-1)$ for an n-vertex graph) so if there are at least 2 vertices of degrees $>2$ then they both have degree 3.
$\endgroup$ 1
