How to prove this necessary and sufficient condition for tree in graph theory?

Question

Let $0<d_1\leq\ldots\leq d_n$ be integers. Show that there exists a tree with degrees $d_1,\ldots,d_n$ if and only if $d_1+\ldots+d_n=2n-2$.

Answer 1

HINT: One direction is easy: if $T$ is a tree with $n$ vertices, then $T$ has how many edges? What does that tell you about the sum of the degrees of the vertices?

For the other direction, first show that if $0<d_1\le\ldots\le d_n$, and $\sum_{k=1}^nd_k=2n-2$, then $d_1=1$. Then prove by induction on $n$ that if $0<d_1\le\ldots\le d_n$, and $\sum_{k=1}^nd_k=2n-2$, then there is a tree with $n$ vertices whose degrees are $d_1,\ldots,d_n$. For the induction step assume that the result is true for $n$, and suppose that $0<d_1\le\ldots\le d_{n+1}$ and $\sum_{k=1}^{n+1}d_k=2n$. You know that $d_1=1$. You also know that if $n\ge 2$, then $d_{n+1}>1$; why? Let $k$ be the smallest subscript such that $d_k>1$. Then

$$0<d_2\le\ldots\le d_{k-1}\le d_k-1\le d_{k+1}\le\ldots\le d_{n+1}\;,$$

and

$$d_2+\ldots+d_{k-1}+(d_k-1)+d_{k+1}+\ldots+d_{n+1}=2n-2\;,$$

so there is a tree with $n$ vertices whose degrees are $d_2,\ldots,d_{k-1},d_k-1,d_{k+1},\ldots,d_{n+1}$. Use this tree to build a tree with $n+1$ vertices whose degrees are $d_1,\ldots,d_{n+1}$.