How many trees are there on 7 vertices, where vertices 2 and 3 have degree 3, 5 has degree 2, and all others have degree 1?

Question

How many trees are there on 7 vertices, where vertices 2 and 3 have degree 3, 5 has degree 2, and all others have degree 1?

So far, I am able to determine that vertices 1, 4, 6, and 7 are leaves. My intuition also tells me this problem involves inclusion/exclusion somehow, but I can't quite figure out what values to calculate.

Answer 1

I believe I've figured out the solution:

The four vertices of degree 1 are leaves.

This implies that vertices 2, 3, and 5 must be adjacent.

There are three distinct ways to connect vertices 2, 3, and 5.

$$ 2 \to 3 \to 5$$ $$ 3 \to 5 \to 2$$ $$ 5 \to 2 \to 3$$

In the first case we must connect two leaves to vertex 2, one leaf to vertex 3, and one to vertex 5. This gives (4 choose 2)(2 choose 1)(1 choose 1) = 12 trees.

In the second case we must connect two leaves to vertices 2 and 3. This gives (4 choose 2)*(2 choose 2) = 6 trees.

The third case is essentially equivalent to the first, where there are 12 trees.

In total, $12+6+12=30$ trees can be formed with the given specifications.

Let me know if my logic is sound.

Answer 2

In order for the tree to be connected the root has to be either vertex $2$, $3$ or $5$. Starting from that point we can now pretty easily enumerate all graphs based on those roots since the tree with root degree $2$ must have either vertices $2$ and $3$ as direct children, and the rest of vertices as leaves, or it must have $2$ or $3$ as one child and a leaf as the other. Continuing in this fashion you can enumerate all trees by hand. I hope someone comes up with a better way :).