Counting problem (should use Cayley's formula)

250 Views Asked by At

How many trees above $V=\{1,2,3,4,5,6,7,8,9\}$ are there, such that $deg(4)=5$?
I know I should use Cayley's formula somehow.

1

There are 1 best solutions below

0
On BEST ANSWER

A hint:

Since there is no "general $n$" in sight I'd suggest to go through the cases and forget about Cayley's formula.

There are ${8\choose 3}=56$ ways to choose the three vertices which are not in the star of $4$.

Assume that the vertices $1$, $2$, $3$ are not in the star of $4$ and count the ways to connect these vertices to $4$ via the vertices $5$–$9$. At the end multiply by $56$.