Find the number of trees on the vertex set V = {1, 2, ..., 8} in which all vertices have degree 1 or 4.

Question

I am unclear how to figure this out. I understand that if there were 6 vertices of deg = 1 and 2 vertices of deg = 4 then I can simply check if the degrees all add up to 2n-2 and use a specific thm: (n-2)!/[(deg_1 - 1)!...(deg_n - 1)!] but that same thm does not seem to apply in this case because I do not have the specific degrees for each vertex. Would I use Cayley's thm to solve this where we have n^(n-2) trees?

Answer 1

HINT:

• How many edges does a tree on $8$ vertices have?
• What is the sum of the degrees of its vertices?

Use the answers to those two questions to show that there is a unique unlabelled tree that satisfies these conditions. Then count the inequivalent ways to label the vertices of that tree with the integers $1,\ldots,8$. (This last step is a fairly simple counting problem.)