Prove that a sequence of positive integers $d_1, d_2, \ldots, d_n$ is a degree sequence of a tree if and only if $d_1+d_2+\ldots+d_n = 2(n-1)$
$(\Rightarrow)$ This follows from the handshaking lemma.
$(\Leftarrow)$ Suppose that for all $k < n$, the statement holds. Now, let $d_n \geq d_{n-1} \geq \ldots \geq d_1$, with $d_1+d_2+\ldots+d_n = 2(n-1)$. Note that $d_1 = 1$. Otherwise, $\sum\limits_{k=1}^n d_k > 2(n-1)$.
I don't really know how to proceed from here. It isn't the case that a simple graph with this property is a tree, and there are too many cases and caveats to take care of in the inductive step. Does anyone know a better/cleaner way to solve the problem?
Let me begin with a rough idea for the induction step and afterward fill the gap in it. The rough idea is to imagine $n$ vertices, the $i$-th one being equipped with the appropriate number $d_i$ of half-edges; the task is to join these half-edges in pairs to make whole edges, forming the desired tree. Begin with the two vertices of highest degree ($d_n$ and $d_{n-1}$) and join them (i.e., join a half-edge from one with a half-edge from the other). Think of this cluster of two vertices as a single big vertex; it has $d_n+d_{n-1}-2$ half-edges remaining, with which it is to be joined to the remaining vertices. So, keeping the other $n-2$ vertices unchanged but counting the cluster as a single vertex, we have $n-1$ vertices with total degree $d_1+d_2+\dots+d_{n-1}+d_n-2=2(n-1)-2=2((n-1)-1)$. So the induction hypothesis says that we can join these up to form a tree; that also makes the original $n$ vertices into a tree.
The gap in this argument is that, to apply the induction hypothesis, I need to know that the degrees are positive integers. That is, I need to know that $d_n+d_{n-1}-2$ is positive. Since $d_n$ and $d_{n-1}$ are positive, the only thing that can go wrong is that they're both $1$, so $d_n+d_{n-1}-2=0$. But $d_n$ and $d_{n-1}$ were the two largest $d_i$'s, so then all the $d_i$ would have to be $1$, their sum would be $n$, so $n=2(n-1)$, and $n=2$. But then we don't need to use the induction hypothesis; just join the two vertices and you're done.