For trees with $10$ vertices, consider those which have a vertex of degree $8$. What is the number of such trees?

Question

I'm trying to figure out what is the flaw in my thinking for this practice question. If a tree has $10$ vertices, one of which must have degree of $8$, this means that we essentially have a $K_{1,8}$ star. So the extra vertex can go in one of 8 places, so wouldn't the number of such trees be $8$?

However, the answers provided says it says the answer is $8\cdot10\cdot9 = 720$ ??

What am I misunderstanding about this question?

Many thanks!

Answer 1

The distinction is that there are $10 \times 9$ inequivalent ways of labeling the $K_{1,8}$ subgraph.

• We choose one of the $10$ vertices to be the degree-$8$ vertex.
• Then, one of the remaining $9$ vertices to be its non-neighbor.
• Then, we attach the non-neighbor to one of the $8$ leaves of $K_{1,8}$. (Your step.)

This gives $10 \times 9 \times 8$.

Answer 2

I think what the question is asking is if we have a graph $K_{10}$ how many spanning trees does this graph have with a vertex of degree $8$ up to labelling.

There are $10$ ways to select which of the vertices is going to be the one with degree $8$ and then there are $9$ ways to select which of the vertices are the neighbors of $v$.

Finally there are $8$ ways to select which of the neighbors is connected to the remaining vertex.

So the answer is $10\cdot9\cdot8$

Answer 3

Pick the vertex $v$ which has degree 8. This is $\dbinom{10}{1}$

9 vertices left. Pick the 8 vertices those are adjacent to $v$. This is $\dbinom{9}{8}$

Now we have one vertex more. Connect it to one of the 8 vertices. That is $\dbinom{8}{1}$

The result follows easily.

Answer 4

If a tree on 10 vertices has a vertex of degree 8, up to isomorphism there is only one such tree, namely the one you mention. (Thus, the number of unlabeled trees on 10 vertices having a vertex of degree 8 is 1 rather than 8.)

But if we want to determine the number of labeled trees - so two trees are considered distinct if, after assigning the vertices the labels $1,2,\ldots,10$, the edge sets are distinct - then the answer is obtained as follows. The label for the central vertex of degree 8 can be picked in 10 ways. Of the remaining 9 labels, the unique vertex of distance 2 from the central vertex can be picked in 9 ways. And this vertex can be made adjacent to one of the remaining 8 vertices in 8 ways. Thus, the number of labeled trees is $10 \times 9 \times 8$.