Induction and Trees Let $d_1, d_2, \ldots, d_n$ be $n$ positive integers, with $n ≥ 2$.
Prove: there exists a tree with vertex degrees $d_1, d_2, \ldots, d_n$ if and only if the sum $d_1 + d_2 + \cdots + d_n = 2n − 2$. 
(Prove in both directions. Use induction for one of them.) 
Note: It is not true that every $n$-vertex graph whose degrees sum to $2n − 2$ is a tree.
Okay, so I am having difficulty understanding the significance of $2n - 2$. I have drawn out multiple trees and counted them up through explorations, but I cannot find a relationship. How should I think about approaching this, and where does induction come into play?
 A: A tree by definition has no loops. Equivalently, you can designate any vertex as the root, and then explore neighbors, without ever visiting the same vertex twice. 
So if you have a tree $T$, lets count the edges. We explore the tree in order 1,2,3,... ,where we label the vertices in order of being visited. Each vertex has degree $d_i$. Vertex 1 has $d_1$ edges. Since we are visiting from a parent vertex, the actual contribution of each subsequent neighbor is $d_i-1$. Thus:
$\sum_{i=1}^nd_i=n-1+d_1+\sum_{i=2}^n(d_i-1)=n-1+E$.
On the other hand, for any graph, $\sum_{i=1}^nd_i=2E$. 
Thus $n-1+E=2E$, or $E=n-1$, which implies $\sum_{i=1}^nd_i=2n-2$.
Can you try finishing the other direction yourself?
A: The $2n-2$ term means that if you have $1$ vertex, you replace $n$ by $1$, if you have $2$, you replace $n$ by $2$, and so forth.

The case $n=1$ is trivial. Suppose there exists a tree with one vertex. Then its degree is necessarily $d_1=0$, and the equality $d_1=2(1)-2=0$ holds. Conversely, if $d_1=0$ holds, then the graph only has one vertex, which is a tree indeed. 
Consider a tree with vertex degrees $d_i$, with $i=1,...,n+1$. This tree has a leaf. Consider the tree without this leaf. Since it has $n$ vertices, the equality $\sum_{i=1}^n d_i=2n-2$ holds. Consider another leaf, and insert a vertex $u$ between this leaf and the tree. It has degree $2$. Therefore
$$\sum_{i=1}^n d_u+2=(2n-2)+2 = 2(n+1)-2$$
Can you figure out the other direction?
