Let $n \ge 9$. How many trees are there on vertex set $[n]$ such that at least one vertex has degree $n-3$?

Question

It is easy to show that a tree with $n \ge 9$ can have at most one vertex of degree $n-3$. Call it $v_0$.

Now, there are $n-1-(n-3)=2$ vertices that are not adjacent to $v_0$, call them $v_{n-1}$ and $v_{n}$. Then a desired tree can be of 3 possible forms:

1. $n-4$ out of the $n-3$ neighbors of $v_0$ are leaves, except for $v_k$, which has degree $2$ and is adjacent to both $v_0$ and $v_{n-1}$. $v_{n-1}$ has degree $2$ and is adjacent to $v_k$ and $v_{n}$. $v_n$ is a leaf.

2. $n-5$ out of the $n-3$ neighbors of $v_0$ are leaves, except for $v_j$ and $v_k$. $v_j$ has degree $2$ and is adjacent to $v_0$ and $v_{n-1}$. $v_k$ also has degree $2$ and is adjacent to $v_0$ and $v_n$. $v_n$ and $v_{n-1}$ are both leaves.

3. $n-4$ out of the $n-3$ neighbors of $v_0$ are leaves, except for $v_k$, which has degree $3$ and is adjacent to $v_0$, $v_{n-1}$ and $v_n$. $v_n$ and $v_{n-1}$ are both leaves.

It is then easy to computer the number of trees in each form and sum them up. My question: is there a cleverer way to count?

Please help. Many thanks in advance!

Answer 1

Note: I corrected a huge logical error in my original edit.

---

It is a little easier to use this generalization of Cayley's formula:

The number of labeled trees on $n$ vertices with degree sequence $(d_1,\dots,d_n)$ is $$\binom{n-2}{d_1-1,d_2-1,\dots,d_n-1}.$$

For trees with one vertex of degree $n-3$, the only possible degree sequences are permutations of one of the following:

• $(n-3,3,1,\dots,1)$.

• $(n-3,2,2,1,\dots,1)$.

To see this, note that for a tree, the sum of $(\deg v-1)$ as $v$ ranges over vertices is $n-2$, and on of the vertices has $\deg v-1=n-4$, so the remaining $(n-2)-(n-4)=2$ can either be given to a single vertex, or two different vertices.

You can then sum up, for each of these sequences, the number of permutations of that sequence, times the corresponding multinomial coefficient. This method has about the same amount of accounting, but not need to draw any actual trees.

Answer 2

Pick a vertex $v$ of degree $n-3$: $n$ choices.

Pick the non-neighbors of $v$: $\binom{n-1}{2}$ choices.

Let $u$ be the smaller non-neighbor of $v$, and let $w$ be the neighbor of $v$ on the $u$-$v$ path. There are $n-3$ choices for $w$.

Now there are $n-1$ choices for the larger non-neighbor of $v$: adjacent to a neighbor of $v$, adjacent to $u$, or subdividing the $uw$ edge.

Total number of choices: $n \binom{n-1}{2} (n-3)(n-1)$.