Induction and Trees

Question

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?

Answer 1

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?

Answer 2

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?