2
$\begingroup$

Let G = (V, E) be a tree. Prove that at most one vertex can have degree at least |V |/2 + 1.

I tried to solve this by using a proof by contradiction. I assumed that at least two vertices can have a degree of |V |/2 + 1. But It didn't help that much. Any ideas?

$\endgroup$
2
  • 5
    $\begingroup$ Hello :) Try to prove, that they have two common neighbors. What does it mean? $\endgroup$
    – Jochen
    Nov 22, 2021 at 20:13
  • $\begingroup$ This is a problem in my discrete math course where it is a violation of academic integrity to get help from websites like StackExchange. I've flagged this question, but figured it would be helpful to add a comment. $\endgroup$ Nov 23, 2021 at 18:54

1 Answer 1

2
$\begingroup$

Let $v_1,v_2$ be two vertices of the tree. Then there is a unique path $v_1,...,v_2$. Remove any of the edges of this path. We get two connected components, each containing one of $v_1$ and $v_2$. At least one of the two connected components contains no more than $|V|/2$ vertices. The one $v_1$ or $v_2$ in that component will have to have degree no more than $|V|/2$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .