trees on six vertices 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?
 A: 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.
A: 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. 
