Graph theory: Tree holds two sub-tree with an amount of vertices

Question

I was asked the following question:

Let $T=\left(V,E\right)$ be a tree, and let $d$ be the maximum degree of a vertex in that tree. Assume that $d \geq 2$. Prove there an edge in the tree such that, when we remove it from $T$, we will get two trees each of which has at most $\left\lceil \dfrac{d-1}{d}\left|V\right|\right\rceil$ vertices.

I tried going by induction on $d$ the maximum degree while I set the number of vertices and it didn't worked. also tried to do induction on the number of vertices and it didn't worked too.

Thanks for the help, Yoav

Answer 1

Hint:

• Find a vertex $v$, such that the size of all components of $T \setminus \{v\}$ is at most $\frac{|T|-1}{2}$.
• There will be at most $d$ such components, let $C$ be the biggest one.
• Your edge will be the one that connects $v$ to $C$ in $T$.

I hope this helps $\ddot\smile$