Verify directly that are exactly 125 labelled trees on 5 vertices.

Question

I know Cayley's formula. However, I need to count them without using the formula. Such a tree has $5-1=4$ edges. Let the degrees of vertices be $d_1,d_2,d_3,d_4,d_5$. By handshaking lemma $d_1+d_2+d_3+d_4+d_5=8$. After from this point I can count them considering every possibility like $d_1 = 4$, then $d_2=d_3=d_4=d_5=1$ etc. However, I need an elegant way to count them.

Answer 1

Well, I personally wouldn't expect a particularly elegant way to count them, but maybe I'm overlooking a particularly beautiful argument here (different from Cayley's formula).

The problem with considering complete degree sequences is that it is not immediately clear from a given sequence whether or not it occurs as the degree sequence of a graph (though it can be done).

To me, the most obvious line of attack is to first classify all non-isomorphic trees on five vertices, and then determine the number of ways to label each of these (modulo isomorphism). The following hint contains some spoilers:

Hint. There are only three non-isomorphic trees on 5 vertices. A picture of this classification can be found through a simple Google search. The proof for this classification is explained here: http://math.stackexchange.com/a/537309 . Note that you do indeed use some information about the degrees of the vertices, but not the entire degree sequence.