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?
Best Answer
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$.