Existence of tree for a given degree sequence.

Question

Let $(d_1,..., d_n)$ be a sequence of positive integers with $\sum_{i=1}^n d_i=2(n-1)$. Then there exists a tree $T$ with vertex set $v_1,..., v_n$ and $d(v_i)= d_i , 1\leq i \leq n$.

My attempt:- For $n=1$ result is vaccously true. Assume result true for $n=k$, that is Let $(d_1,..., d_k)$ be a sequence of positive integers with $\sum_{i=1}^k d_i=2(k-1)$. Then there exists a tree $T$ with vertex set $v_1,..., v_k$ and $d(v_i)= d_i , 1\leq i \leq k$. we want to prove the result for $n=k+1$, Let $(d_1,..., d_{k+1})$ be a sequence of positive integers with $\sum_{i=1}^{k+1} d_i=2(k-1)+2=\sum_{i=1}^k d_i+2$. So, $d_{k+1}=2$

Let $(d_1,..., d_k)$ be a sequence of positive integers with $\sum_{i=1}^k d_i=2(k-1)$. Then there exists a tree $T$ with vertex set $v_1,..., v_k$ and $d(v_i)= d_i , 1\leq i \leq k$.

Let $T$ be the required tree. If we add a vertex then degee must be equalls to two. Since $T$ is a tree the it must have atleast two pendant vertices. choose one of the pendant vertex, $x$(say). If we add a verex here and attach an edge to $x$ degree of $x$ changes to two. interchange the adding vertex and pendant vertex. we get the desired tree. Is my arguments correct?

Answer 1

No, you cannot assume that $\sum_{i=1}^k d_i=2(k-1)$ in the induction step, so the argument that $d_{k+1} = 2$ is invalid.

Answer 2

Even better, this is an if and only if statement.

Let $v_1,...,v_n$ be positive integers with $n\geq 2$.

Proof: ($\Rightarrow$) Assume that there exists a tree $T$ with degree sequence $v_1,...,v_n$. Since $T$ is a graph, we use the Degree-Sum Formula to have $\sum_{i=1}^n(d_i)=2e(T)$. Since $T$ is a tree, we know that there are $n-1$ edges in $T$. Hence, $\sum_{i=1}^n(d_i)=2(n-1)$. Thus, if $T$ has a degree sequence of $v_1,...,v_n$, then $\sum_{i=1}^n(d_i)=2n-2$.

($\Leftarrow$) Assume that $\sum d_i=2n-2$. We show by induction on $n$ that there exists a tree with vertex degrees $v_1,...,v_n$.

Basis Step: $n=2$. $\sum d_i=2(2)-2=2$. Since $n=2$, there exist two positive integers, neither of which can be greater than $2$, as then adding the two numbers together would be greater than $2$. Since $0<d_1<2$, and $0<d_2<2$, and both are integers, it must be the case that $d_1=1$, and $d_2=1$. Consider these two numbers as vertices with degree $1$, hence they are adjacent to each other. This creates the path $P_2$, and therefore exists a tree.

Induction Step: $n>2$. We assume that the claim holds for $n-1$ positive integers $v_1,...,v_{n-1}$. Let $G$ be an arbitrary graph with $n$ vertices such that the degree sequence of $G$ is $v_1,...,v_n$. We know that such a graph $G$ exists as the sum of the degree sequence is even. In addition, it must be the case that there exists at least one vertex $v$ with $d(v)=1$. To show this, suppose on the contrary that $d(i)\geq 2$ for all $i\in [n]$. Thus, the sum of degrees $$\sum\limits_{i=1}^nd(i)\geq 2n>2n-2$$ which is a contradiction. Consider the subgraph $G-v$. By deleting such a vertex of degree one, we delete one edge from $G$. This means that the resulting graph $G-v$ has $n-1$ vertices and the sum of degrees is $2n-4=2(n-1)-2$. Thus, it is possible that $G-v$ is constructed in such a way that it is a tree. Hence, adding the leaf $v$ back to $G-v$ when $G-v$ is constructed as a tree, results in $G$ being a tree. Thus, if $\sum d_i=2n-2$, there exists a tree with vertex degrees $v_1,...,v_n$.

Therefore, there exists a tree $T$ with vertex degrees $v_1,...,v_n$ if and only if $\sum d_i=2n-2$.