3
$\begingroup$

I have a labelled tree with $n$ vertices for $n > 1$. How do I find the number trees with vertices tree that has a degree of $n-2$? I have been trying to figure it out but cannot seem to solve it. Is there any theorems that would help me with this?

I have tried using the Prufer sequence to solve it. I saw a pattern that if a vertex in the Prufer sequence shows up $n-2$ times, then that graph has a vertex with degree $n-2$. However, I am not sure how to work out the Prufer sequence for the larger number of vertices without drawing all the graphs which is not ideal.

$\endgroup$
3
  • $\begingroup$ Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or closed. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$ May 15 '20 at 8:12
  • $\begingroup$ @JoséCarlosSantos Thank you for the suggestion. I have edited the post with better context to the problem. $\endgroup$ May 15 '20 at 8:16
  • 2
    $\begingroup$ @FatimahFatCakes +1 for doing so. $\endgroup$ May 15 '20 at 8:28
2
$\begingroup$

First we have to find out how such a tree looks like. Note that a tree with $n$ vertices has exactly $n-1$ edges. Since $n-2$ of these have to emanate from a single vertex there are not many possibilities left.

Given the possible unlabeled trees you have to find out in how many different ways you can label these trees with the numbers $1$, $2$, $\ldots$, $n$.

$\endgroup$
1
  • $\begingroup$ I have used Cayley's formula and found out that there are n^(n-2) possible graphs. However, I am not sure how to find out how many shapes there are? for $n=4$, I know that there are 4 different shapes. Would the number of different shapes simply be $n$? As for how many ways I can label the vertices of a shape, that would be $n$ different ways. $\endgroup$ May 15 '20 at 8:31
2
$\begingroup$

The Prufer sequence approach would also work (except that your condition should be that a vertex appears exactly $n-3$ times*). You should be able to count the number of such sequences. All that matters is which vertex appears $n-3$ times, which other vertex appears, and which position the other vertex appears in - how many possibilities is this?

*Note that a vertex of degree $k$ appears exactly $k-1$ times in the Prufer sequence. This is because as you construct the sequence you remove leaves one by one. If a vertex $v$ has degree $k$, then $k-1$ of its neighbours must be removed before it becomes a leaf, and each time this happens $v$ is added to the sequence. Once $v$ becomes a leaf, either it is removed itself or $v$ and its remaining neighbour are the final two vertices. In neither case is it added to the sequence again.

$\endgroup$
3
  • $\begingroup$ Can you elaborate more on why my condition should be that a vertex appears exactly $n-3$ times? $\endgroup$ May 15 '20 at 8:34
  • 2
    $\begingroup$ @FatimahFatCakes yes, edited $\endgroup$ May 15 '20 at 8:41
  • $\begingroup$ Got it! Thank you for your explanation. It really helped me understand it well. $\endgroup$ May 15 '20 at 9:02

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.