Prove in any tree with n vertices, the number of nodes with 3 or more neighbors is at most 2(n-1)/3

937 Views Asked by At

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.

1

There are 1 best solutions below

4
On BEST ANSWER

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.