Let $T(n,k)$ be the maximum number of vertices with degree $\geq k+1$ for non-root vertices, and $\geq k$ for roots, in any set of trees with $n$ vertices total.
Is there a closed formula for $T(n,k)$?
I know the solution for $n = 32, k = 4$, but I want to know the more general solution
Best Answer
First, let $T'(n,k)$ denote the maximum possible number of vertices of degree at least $k$ in a tree on $n$ vertices. Let $G$ be such a tree. Then \begin{align}2(n-1)=2\big|E(G)\big|&=\sum_{v\in V(G)}\deg v\\&=\sum_{\deg v\ge k} \deg v+\sum_{\deg v <k}\deg v\\&\ge k\cdot T'(n,k)+1\cdot \big(n-T'(n,k)\big)\\&=n+(k-1)T'(n,k).\end{align} This shows that $T'(n,k)\le \left\lfloor\frac{n-2}{k-1}\right\rfloor$. It is easy to see that there is such a tree with exactly $\left\lfloor\frac{n-2}{k-1}\right\rfloor$ vertices of degree $k$, so $$T'(n,k)= \left\lfloor\frac{n-2}{k-1}\right\rfloor.$$ The example below shows that $T'(33,4)=10$ (the green vertices are the vertices of degree $\ge 4$).
Now, to find $T(n,k)$, let $G$ be a rooted tree on $n$ vertices such that the number of non-root vertices of degree at least $k+1$, plus one if the root has degree at least $k$, is $T(n,k)$. Then add an extra vertex to $G$ with an edge connecting this extra vertex to the root, and call this new graph $G'$. Then, $G'$ is a graph on $n+1$ vertices with at least $T(n,k)$ vertices of degree at least $k+1$. Therefore by the previous paragraph, $$T(n,k)\le T'(n+1,k+1)=\left\lfloor\frac{(n+1)-2}{(k+1)-1}\right\rfloor=\left\lfloor\frac{n-1}{k}\right\rfloor.$$ It is easy to see that this is indeed an equality. The example below shows that $T'(28,4)=6$ (the red vertex is the root with degree $\ge 4$, and the green vertices are the non-root vertices of degree $\ge 4+1=5$).