Question

Let d1, d2, ..., dn, with n at least 2, be positive integers. Use mathematical induction to explain why, if d1+ d2+…+dn = 2n-2, then there must be a tree with n vertices whose degrees are exactly d1, d2, ..., dn. (Be careful with reading this statement. It is not the same as saying that any tree with vertex degrees d1, d2, ..., dn must satisfy d1+ d2+...+dn = 2n-2, although this is also true. Rather, it says that if you begin with the numbers d1, d2, ..., dn, then you can find such a tree.) Note: For this problem we are concerned with the total degree. Normally in trees we are only concerned with out-degree and usually just say "degree" since the in-degree is always fixed at one in a tree.

Answer 1

Assume di = 2n − 2 where the di’s are all positive integers. Proceed by induction on the number if integers in the sequence d1, d2, · · ·, dn.

Base Step: n = 2. Then 2n − 2 = 2, and the sequence must be 1,1 which is the degree sequence of K2.

Inductive Step: Assume the conclusion holds for all acceptable sequences of length n − 1 or less. Recall that by assumption, the smallest integer in the sequence is at least 1. On the other hand, the average of di’s is (2n − 2)/n = 2 − 2/n < 2.

So, at least one of the di’s is exactly 1, call it dn, and at least one of the di’s is at least 2, call it dn−1. Since the sequence d1, d2, · · ·, dn−2, (dn−1) − 1 consists of all positive integers and di = (2n − 2) − (2) = 2(n − 1) − 2, the inductive hypothesis implies that there exists a tree on n − 1 vertices with this degree sequence. To this tree, add an additional leaf to whichever vertex has a degree (dn−1)− 1 and we have a tree with the original degree sequence.