number of trees with 10 node

Question

How many trees with 10 nodes are there, given that each vertex must have a degree of either 1, 2, or 5?

I initially approached the problem by attempting to construct each tree individually, focusing first on maximizing the number of edges with vertices of degree 5, then proceeding similarly for vertices of degree 2. However, this method proved to be time-consuming and lacked certainty regarding the completeness of the solution. Is there a more efficient strategy for solving such problem?

Answer 1

This is a way to make trial and error easier

Using Euler characteristic for planar graphs with no faces we get number of edges must always be equal to 9 which is evident from your tries

Since number of edges are known sum of degrees for all vertices must be 18

Let $x_n$ be the number of vertices with degree n

We have $$x_1+x_2+x_5=10\\x_1+2x_2+5x_5=18$$

This leads to 3 integral solutions $$(2,8,0)\\(5,4,1)\\(8,0,2)$$

The first and third are easy and yield only one graph each since no degree 1 node can be anywhere but the end of a chain

As far as I am aware you need trial and error for second

Edit: OK so my awareness just increased for second one consider the graph with one long chain if you take off a node at one end and attach it to a free degree one node the number of degree one and degree two nodes don't change

So my idea here is first we fix a one degree on one edge of degree 5 (since this is necessary given the numbers) now since we can make a side chain of every length $\ge1$ we just find the number of partitions of 8 so $$1,1,1,5\\1,1,2,4\\1,1,3,3\\1,2,2,3\\2,2,2,2$$

This means your seven graphs are exhaustive

Answer 2

The number of vertices $v=10$. Hence the number of the edges is $e=v-1=9$. The sum of degrees of all vertices is $2e=18$ then.

Now let us see how we can split $18$ into a sum of $10$ summands equal to $1$, $2$ or $5$. Consider the number of $5$s. If it is $3$ or more then there is at most $6$ summands which is bad.

If we have two $5$s then we have to get $8$ as a sum of $8$ numbers. They are all ones then.

$18=2\cdot 9$. Hence if there is none $5$s then $18=1+1+2\cdot8$ is the only way in this case.

If there is exactly one $5$ then we have to get $13$ as a sum of $9$ summands. The only way is $13=7\cdot 1+3\cdot 2$.

So we have three possible sets of vertices degrees:

$$5,5,1,1,1,1,1,1,1,1;$$

$$2,2,2,2,2,2,2,2,1,1;$$

$$5,2,2,2,2,1,1,1,1,1.$$

There is only one tree of the first type since two $5$s must be adjacent. Also, there is only one three of the second type since it is easy to see that all $2$s go in chain.

Now the third type. The $2$s all hang on the $5$-vertex. They can be

• on the different branches ($2,2,2,2$),

• or two of them can be together in chain ($22,2,2$),

• or two chains of two $2$s ($22,22$),

• or one big chain ($222,2$),

• or one very big chain ($2222$).

In total, we get $7$ trees.