Here is what I need to prove:
Let $d_1,d_2,…,d_n$ be a sequence of natural numbers (>0). Show that $d_i$ is a degree sequence of some tree if and only if $\sum d_i = 2(n-1)$.
I know that:
1. for any graph $\sum_{v \in V}\ deg(v) = 2e$;
2. for any tree $e=v-1$.
From 1 and 2 it follows that for any tree $\sum_{v \in V}\ deg(v) = 2(v-1)$.
If I understand it correctly, this is only a half of the proof ($\rightarrow$), isn't it?
Any hints on how to prove it the other way?
Edit (induction attempt):
-
$n=1$, we have $d_1 = 2(1-1) = 0$ and $d_1$ is a degree sequence of a tree.
-
Let's assume the theorem holds for all $k<n$. So we know that $d_1 + d_2 + … + d_{n-1} = 2(n-2) $ and that it's a degree sequence of a tree. In order to add one vertex to this tree, so that it remains a tree we only can add a vertex of degree one (we connect it to any existing vertex with a single edge). By doing this our new sequence is $1,d_1,…,d_j+1,…,d_{n-1}$, where $j$ is the vertex to which we attached the new vertex (it's degree increments). Clearly this sums to $2(n-1)$.
Is this proof correct or am I missing the point?
Best Answer
Hints for the other way round: