Answer to Question #281794 in Discrete Mathematics for Nick

Question

How many 5 vertices unlabelled trees are there? How would I draw them?

Answer 1

A tree with 5 vertices has 4 edges. So, the total degree of this graph is 8.

We need to find all degree sequences such that the total degree is 8 and each vertex has degree at least 1.

Let us consider the maximum degree of the graph. Since the graph has 4 edges, it follows that maximum degree $\leq 4$ . Since the total degree is 8, it follows that maximum degree $>8/5$ .

So, $2\leq$ maximum degree $\leq 4$ .

If the maximum degree is 4, then we have the following degree sequnce: (4, 1, 1, 1, 1).

If the maximum degree is 3, then we have: (3, 2, 1, 1, 1).

If the maximum degree is 2, then we have: (2, 2, 2, 1, 1).

There are three unlabelled trees with 5 vertices.