0
$\begingroup$

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!

|cite|improve this question
$\endgroup$
2
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Many thanks. I see what you mean. $\endgroup$ – Terrence J Jun 21 '14 at 4:36
1
$\begingroup$

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$

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Yes with the additional 'up to labelling' this makes it much clearer. $\endgroup$ – Terrence J Jun 21 '14 at 4:37
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.