Score of a tree
Task number: 4214
Let the sequence of numbers \( 1 \le d_1 \le d_2 \le… \le d_n \) be such that \( \sum\limits_{i = 1}^n d_i = 2n-2 \). Prove that \( (d_1,…, d_n) \) is the score of a tree.
Solution
By iduction on number of vertices:
For \( n = 2 \) is \( (d_1, d_2) = (1{,}1) \) and the searched tree is \( K_2 \).
For \( n \ge 3 \), \( d_1 = 1 \), otherwise the sum would be at least \( 2n \). Also it holds that \( d_n> 1 \) as otherwise the sum would be \( n \).
The sequence \( (d_2, d_3,…, d_n-1) \) has the sum \( 2 (n-1) -2 \), i.e. it is according to the inductive hypothesis after a possible rearrangement of the score of a tree. By adding a new neighbor to the vertex of degree \( d_n-1 \), we get the tree we are looking for.
