I am preparing for the final exam, but struggling with these questions.

How many labelled trees with $2n$ vertices such that the vertex with label $1$ has degree $k$, for $k = 1, 2$ and $n$?

Also, A labelled tree with $n$ vertices is chosen randomly from the set of all $n^{n-2}$ labelled trees with $n$ vertices. What is the probability that the vertex labelled $1$ has degree $1$ in this tree? If $n$ is large, what can you say about this probability?

Can anyone help me with these questions in detail? (I am beginner in Graph Theory, so need detail answer to understand it.)


A tree with $2n$ vertices has $2n-1$ edges, so the sum of the degrees of its vertices is $4n-2$. If vertices $1$ through $n$ have degrees equal to their labels, the sum of those degrees is $\frac12n(n+1)$. A tree is connected, so each of the remaining vertices must have degree at least $1$, and the sum of the degrees of all $2n$ vertices must be at least $\frac12n(n+1)+n=\frac12n(n+3)$. It’s not hard to show that $\frac12n(n+3)>4n-2$ for $n\ge 5$, so such a tree is impossible for $n\ge 5$. It’s also clear that there is no such tree for $n=1$, so we need only consider the three cases $n=2$, $n=3$, and $n=4$.

For $n=2$ the only possible degree sequence is $2,2,1,1$; for $n=3$ the only possible degree sequence is $3,2,2,1,1,1$; and for $n=4$ we have only $4,3,2,1,1,1,1,1$ to check. Thus, if $n=2$ the tree must be a chain; vertices $1$ and $2$ can be adjacent or not, and in either case there are two distinguishable ways to label vertices $3$ and $4$, so there $4$ distinct labelled trees in this case.

If $n=3$ there are two unlabelled trees with the right degree sequence:

       d                             *  
       |                              \  
       3---a---b---c                   *  
       |                                \  
       e                                 *---*  

In the first of these there are two choices for vertex $2$, $a$ and $b$. There are also really only two choices for vertex $1$, because $d$ and $e$ are indistinguishable: vertex $1$ adjacent to vertex $3$ (i.e., $d$ or $e$), or not adjacent to vertex $3$ (i.e. $c$). If vertices $1$ and $2$ are adjacent to vertex $3$, the remaining three vertices are all distinguishable: one has degree $2$, one has degree $1$ and is adjacent to vertex $3$, and one has degree $1$ and is not adjacent to vertex $3$. Thus, these three vertices can be labelled $4,5$ and $6$ in $3!=6$ different ways. If vertex $2$ is $a$ and vertex $1$ is $c$, however, $b$ can be distinguished from $d$ and $e$, but $d$ and $e$ can’t be distinguished from each other. Thus, once we decide which of the labels $4,5$, and $6$ to attach to vertex $b$, the labelling is complete, and we get only $3$ labelled trees from this case.

Similarly, there are $3$ labelled trees ways with vertex $2$ at $b$ and vertex $1$ at $c$, and $3!=6$ labelled trees with vertex $2$ at $b$ and vertex $1$ adjacent to $3$. That’s a total of $18$ labelled trees corresponding to the first unlabelled tree. I’ll leave it to you to count the labellings of the second tree; it’s actually a little easier. I’ll also leave to you the $n=4$ case; the two subcases are vertex $3$ adjacent to vertex $4$, and vertex $3$ not adjacent to vertex $4$.

For the second problem, suppose that I have a labelled tree on $n$ vertices with vertex $1$ as a leaf. Then removing vertex $1$ leaves a tree, and if we decrease each of its labels by $1$, we have an ordinary labelled tree on $n-1$ vertices. Conversely, if I start with a labelled tree $T$ on $n-1$ vertices and increase the label of each vertex by $1$, I can then attach a leaf labelled $1$ to any one of the $n-1$ vertices of $T$ to get a labelled tree on $n$ vertices, and all of these labelled trees are distinct. There are $(n-1)^{n-3}$ labelled trees on $n-1$ vertices, and there are $n-1$ ways to attach the new leaf, so there are $(n-1)\cdot(n-1)^{n-3}=(n-1)^{n-2}$ labelled trees on $n$ vertices having vertex $1$ as a leaf. Since there are altogether $n^{n-2}$ labelled trees on $n$ vertices, the probability that a randomly chosen labelled tree on $n$ vertices has vertex $1$ as a leaf is $$\left(\frac{n-1}n\right)^{n-2}=\left(1-\frac1n\right)^{n-2}\;.$$




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.