Let G = (V, E) be an undirected graph and T a tree in G with k ≥ 2 leaves. Prove that the tree T contains at most k − 2 nodes of degree three or more.
This is what I have:
k-2 = the number of internal vertices = the sum of degrees of internal vertices k = the number of leaves
The sum of the degrees is twice the number of edges in the tree, diminished with the number of leaves k, since their edges are only counted in the degrees of their parents:
= 2 − k
Because the number of edges in the tree is one less than the number of vertices, we also have:
= k-2 + k − 1
So we can substitute the in the first equation:
= 2(k-1+k − 1) - k= 3k-6
We then divide s/k-2=3 Would this be the correct way of getting a solution or is it better to use the average degree of a tree formula $\frac{2(n-1)} n$ Where we still get 3?