Graph Theory: labelled tree

Question

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

Answer 1

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}\;.$$

Finally,

$$\lim_{n\to\infty}\left(1-\frac1n\right)^{n-2}=\left(\lim_{n\to\infty}\left(1-\frac1n\right)^{-2}\right)\left(\lim_{n\to\infty}\left(1-\frac1n\right)^n\right)=1\cdot\frac1e=\frac1e\;.$$