How many trees over ${1,2,3,...n}$ with conditions

Question

I’m stuck on this question in graph theory. The question is:

How many labeled trees are there over $V={0,1,2,...n}$ with which vertices 1,2,3 are leaves, and distance between any two of these leaves is 3 or more.

I tried using Cayley theorem but I don’t know how to apply it in this specific question.

Answer 1

Like every other question about counting trees, this can be answered using Prüfer codes.

Each tree with vertex set $\{1,2,\dots,n\}$ corresponds to a unique Prüfer code, which is a sequence of $n-2$ elements of $\{1,2,\dots,n\}$. Moreover, a vertex of degree $k$ in the tree appears $k-1$ times in the Prüfer code.

So to count the trees which have $1$, $2$, and $3$ as leaves, it suffices to count Prüfer codes which don't include the elements $1$, $2$, and $3$. There are $(n-3)^{n-2}$ of these.

To deal with the condition that these leaves are distance $3$ apart, it's easiest to use inclusion-exclusion. Starting with the quantity $(n-3)^{n-2}$,

• subtract the number of trees that have $1$, $2$, and $3$ as leaves, with $1$ and $2$ only distance $2$ apart.
• subtract the number of trees that have $1$, $2$, and $3$ as leaves, with $1$ and $3$ only distance $2$ apart.
• subtract the number of trees that have $1$, $2$, and $3$ as leaves, with $2$ and $3$ only distance $2$ apart.
• add back, twice, the number of trees that have $1$, $2$, and $3$ as leaves, with all three of them only distance $2$ apart.

We can compute these by observing that any tree in which vertices $1$, $2$, and $3$ are leaves, and $1$ and $2$ are distance $2$ apart, can be built by starting with a tree on vertex set $\{1,3,\dots,n\}$ in which $1$ and $3$ are leaves, and adding the vertex $2$ to the unique neighbor of $1$. So there are $(n-3)^{n-3}$ such trees. The other two cases are similar (except in the last case, we add two vertices), so we get a final answer of $$ (n-3)^{n-2} - 3(n-3)^{n-3} + 2(n-3)^{n-4}. $$

---

We can also reason more directly, though this requires making use of more details of the Prüfer code. From the algorithm to convert a tree into a Prüfer code (see the Wikipedia article for details) it is clear that when vertices $1$, $2$, and $3$ are all leaves, the first number in the code is the parent of vertex $1$, the second number is the parent of vertex $2$, and the third number is the parent of vertex $3$.

All three of these numbers must be different to ensure that the three vertices are not too close together. Therefore the number of ways to choose a Prüfer code for such a tree is the product of:

• $n-3$ ways to choose the first number out of $\{4,5,\dots,n\}$;
• $n-4$ ways to choose the second number out of $\{4,5,\dots,n\}$, different from the first;
• $n-5$ ways to choose the third number out of $\{4,5,\dots,n\}$, different from the first and second;
• $(n-3)^{n-5}$ ways to choose the remaining $n-5$ numbers out of $\{4,5,\dots,n\}$.

The product of these is $(n-3)^{n-4}(n-4)(n-5)$, which is equivalent to the previous formula.