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

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.

• See this question, which is a duplicate of this one but contains an elegant solution within the question. Jun 9, 2018 at 19:22

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.

• Very nice! But you need to add the last term twice (since you subtracted it three times instead of once). (E. g. for $n=4$, the result should be $0$, not $-1$.) Jun 7, 2018 at 19:06
• @joriki You're right! I just now came to this conclusion myself, after messing around with Mathematica for ten minutes to figure out which cases I was missing. Jun 7, 2018 at 19:09
• That happens to be $(n-3)^{n-4}(n-4)(n-5)$. I wonder if these factors of $n-4$ and $n-5$ can be seen more directly from the structure of the trees. Jun 8, 2018 at 2:16
• @AlexanderBurstein I don't know if there's a graph-theoretic approach, but here's another solution using Prüfer codes that gives this factorization instead. (It's simpler, but it requires thinking about Prüfer codes more closely, which many people prefer not to do.) Jun 8, 2018 at 2:23
• See this question, which is a duplicate of this one but contains an elegant solution within the question. Jun 9, 2018 at 19:22