1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.