Prove that if $T$ is a tree on at least $k+1$ vertices and max degree at most $d$, then there exists an edge $e$ such that the removal of $e$ causes $T$ to split into two trees where at least one of them has between $k$ and $dk$ vertices.
Obviously I know that if $T$ has at most $dk+1$ vertices then removing an edge leading to a leaf gives what we need. But what if there are more vertices? Where does the max degree come into play?
Thanks.
Pick a vertex $r$ and set it as the root of $T$.
The subtree of $T$ rooted at a vertex $v \neq r$ is the tree induced by $v$ and all its descendants. Denote it by $T_v$ and its number of vertices by $|T_v|$.
Let $ch(r) = \{v_1, v_2, \ldots, v_h\}$ be the children of the root $r$. You can prove that one of the two following holds for any tree $T$ with at least $k + 1$ vertices and maximum degree $d$ :
1) for every $v_i \in ch(r)$, $|T_{v_i}| < k$
2) $T$ has a subtree having between $k$ and $dk$ vertices
which would prove the statement (if 1) holds, removing a leaf edge finds a desired tree, and if 2) holds, one can choose the edge parent to the root of the subtree found).
Suppose there is a tree $T$ for which both do not hold. Then let's assume that $T$ is a minimal counter-example (i.e. the statement is true for all rooted trees with at least $k + 1$ vertices, maximum degree at most $d$ and with strictly less vertices).
Since 1) does not hold, then there is some $v_i \in ch(r)$ such that $|T_{v_i}| \geq k$. If $|T_{v_i}| \leq dk$, then 2) holds. So assume $|T_{v_i}| > dk$.
Since $T$ is minimal and $T_{v_i}$ has at least $k + 1$ vertices and max degree at most $d$, 1) or 2) holds for $T_{v_i}$. If 1) holds, then $T_{v_i}$ has at most $d(k - 1) + 1 < dk$ vertices, contradicting the previous assumption.
So instead suppose that 2) holds. Then $T_{v_i}$ has a subtree having between $k$ and $dk$ vertices, and so does $T$, a contradiction.