Let $k\geq 2$ and $T$ be a tree on $k$ vertices. Let $ D_k = (d_1,\cdots, d_k)$ be a sequence of positive integers. Show that $D_k$ is the degree sequence of $T$ iff $\sum_{i=1}^k d_i = 2k-2.$
For the forward implication, we know that $2|E(T)| = 2(k-1) = 2k-2 = \sum_{i=1}^k d_i$.
For the reverse implication, suppose $\sum_{i=1}^k d_i = 2k-2.$ We want to show that $(d_1,\cdots, d_k)$ is the degree sequence of $k.$ We use induction on $k.$ For $k=2,$ we have $d_1 + d_2 = 2.$ Since both $d_1$ and $d_2$ are positive integers, $d_1 = 1 = d_2,$ and so $(d_1, d_2)$ is the degree sequence of a tree with $k$ vertices. So the base case holds. Now suppose that for all $2\leq k < m, m\geq 3, $ whenever $(d_1,\cdots, d_k)$ is a sequence of positive integers so that $\sum_{i=1}^k d_i = 2k-2,$ $(d_1,\cdots, d_k)$ is the degree sequence of a tree on $k$ vertices. Let $D_{m} = (d_1,\cdots, d_{m})$ be a sequence of $m$ positive integers so that $\sum_{i=1}^m d_i = 2m-2.$ If one $d_i = 2,$ then $D_m[i] := (d_1,\cdots, d_{i-1}, d_{i+1},\cdots, d_m)$ is a sequence of $m – 1$ positive integers with $\sum_{1\leq j\leq n, j\neq i} d_j = 2m-4 = 2(m-1) – 2.$ Thus, by the inductive hypothesis, $D_m[i]$ is the degree sequence of a tree $T_{m-1}$ on $m-1$ vertices. Since $m-1\geq 2, T_{m-1}$ has at least $1$ leaf $t_1$. Add a new vertex $t'$ to $T_{m-1}$ so that $t_1 t'$ is an edge and let $T_{m-1}'$ be the resulting tree. Then $T_{m-1}'$ is a graph with $m$ vertices, and the only difference between the degree sequences of the two trees is that the degree sequence of $T_{m-1}'$ has one more entry of degree $2$. We claim that $T_{m-1}'$ is a tree. Observe that it has $m-1$ edges, since $T_{m-1}$ has $m-2$ edges, and for any two vertices $u \neq t', v \neq t'\in V(T_{m-1}')$ there is a path in $T_{m-1}'\backslash t' = T_{m-1}$ from $u$ to $v$. Also, we can append the neighbour of $t', t_1,$ to the beginning of a path from $t_1$ to any vertex other than $t_1$ and $t'$ ($t'$ and $t_1$ are joined by a path by definition, so we just need to consider vertices distinct from these two). So $T_{m-1}'$ is connected, and hence a tree. Thus, $(d_1,\cdots, d_m)$ is the degree sequence of the tree $T_{m-1}'.$
However, I'm having a lot of trouble dealing with the case where no $d_i=2$, and I can't fully prove it. Is there some simpler approach?
Best Answer
The induction argument that occurs to me is a bit different. Suppose that the result is true for all sequences shorter than $k$ that satisfy the conditions of the theorem, and let $D_k=\langle d_1,\ldots,d_k\rangle$ be a sequence of positive integers such that $\sum_{i=1}^kd_i=2k-2$.
The idea is to remove all of the $1$ terms from the sequence, so that if $D_k$ really is the degree sequence of a tree $T$, we’re removing the pendant vertices. Of course that would also reduce the total degree of the remaining vertices by the number of pendant vertices, so we have to adjust the remaining terms of $D_k$ downward by a total amount equal to the number of $1$ terms. The trick is to do this in such a way that we get a shorter sequence satisfying the conditions of the theorem, so that we can apply the induction hypothesis to get a tree $T'$ and then add the appropriate leaves to to to get a tree $T$ whose degree sequence is $D_k$, and the induction is complete.
If $d_i\ge 2$ for $i=1\ldots,k$, then $\sum_{i=1}^kd_i\ge 2k$, which is impossible, so there is at least one $i$ such that $d_i=1$. (In fact there are at least two.) We may assume that $d_1\le d_2\le\ldots\le d_k$. Let $\ell=\max\{i\in[k]:d_i=1\}$; then
$$\sum_{i=\ell+1}^kd_i=2k-2-\ell=\big(2(k-\ell)-2\big)+\ell\,.$$
If $\ell=k$, then $k=\sum_{i=1}^k1=2k-2$, so $k=2$, and $\langle 1,1\rangle$ is indeed the degree sequence of the tree on $2$ vertices; otherwise $\sum_{i=\ell+1}^kd_i\ge\ell$.
If $\sum_{i=\ell+1}^kd_i=\ell$, then $2k-2=2\ell$, so $\ell=k-1$, and we have the degree sequence of the tree $K_{1,k-1}$. Otherwise, $\sum_{i=\ell+1}^kd_i>\ell$. And
$$\sum_{i=\ell+1}^k(d_i-1)=2k-2-\ell-(k-\ell)=k-2\,,$$
so $k-2>\ell-(k-\ell)$, $2k-2>2\ell$, $k-1>\ell$, and $\sum_{i=\ell+1}^k(d_i-1)\ge\ell$.
Let $m$ be maximal such that $\sum_{i=\ell+1}^m(d_i-1)\le\ell$. For $i=1\ldots,m-\ell$ let $d_i'=1$, and if $m<k$ let $d_{m-\ell+1}'=\sum_{i=\ell+1}^{m+1}(d_i-1)-\ell+d_{m+1}$. If $m+1<k$ let $d_i'=d_{\ell+i}$ for $i=m-\ell+2,\ldots,k-\ell$. Then
$$\sum_{i=1}^{k-\ell}d_i'=\sum_{i=1}^kd_i-2\ell=2(k-\ell)-2\,,$$
so by the induction hypothesis $\langle d_1',\ldots,d_{k-\ell}'\rangle$ is the degree sequence of a tree $T'$ on $k-\ell$ vertices. Let the vertices of $T'$ be $\{v_1,\ldots,v_{k-\ell}\}$, and let $d(v_i)=d_i'$ for $i=1,\ldots,k-\ell$. For $i=1,\ldots,m-\ell$ attach $d_{\ell+i}-1$ leaves to $v_i$, and attach $\ell-\sum_{i=\ell+1}^m(d_i-1)$ leaves to $v_{m-\ell+1}$, if that vertex exists. The resulting tree has $k$ vertices and degree sequence $\langle d_1,\ldots,d_k\rangle$.