I know that the number of edges in the tree is n-1, and by the sum identity, the degree is 2(n-1)... I'm not sure how to go about completing the proof, or even starting it for that matter.
Asked
Active
Viewed 936 times
1 Answers
1
Since the sum of the degrees is $2(n-1)$ assume there are more than $\frac{2(n-1)}{3}$ vertices of degree $3$ or more, then the sum of the degrees is more than $3\times \frac{2(n-1)}{3}=2(n-1)$, a contradiction.
Asinomás
- 105,651
-
Okay, so how do we know that there are no more than 2(n-1)/3 vertices of degree 3 or more? – user1822739 Jan 24 '15 at 06:22
-
if we had more than (2n-1)/3 of degree 3 or more, the sum of the degrees would be more than 2(n-1), which is impossible. – Asinomás Jan 24 '15 at 06:23
-
Ahhh, I see. Thank you for your help! – user1822739 Jan 24 '15 at 06:24
-
Sure, happy to do so. – Asinomás Jan 24 '15 at 06:26