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.
 A: 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.
