# Prove that at most one vertex can have degree at least |V |/2 + 1. [closed]

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?

• Hello :) Try to prove, that they have two common neighbors. What does it mean? Nov 22, 2021 at 20:13
• 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. Nov 23, 2021 at 18:54

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$$.