Graph theory tree rank sequence

Question

let $T=(V,E)$ be a tree with $n$ vertices , which his degree sequence is $d_1 \le d_2 \le ... \le d_n$ if and only if $d_1\gt 0$ and $d_1+d_2+...+d_n=2(n-1)$ $$$$ i managed to prove it one direction with indaction... but for days im not able to prove its a tree...(in the other direction). Please help me or guide me how to solve it

Answer 1

I suppose that you've proven that if $T$ is tree than $d_1\gt 0$ and $d_1+d_2+...+d_n=2(n-1)$.

Lets move in the other direction. We will prove that if $d_1 >0$ than the graph is connected. We will prove that by induction. The case of $n = 2$ is obvious. Suppose we've proven that for $n = k$. Check the case of $n = k + 1$. If it's not connected then we have connected components of smaller size $\{C_k\}, k = 1, 2,\dots, m$. Each component is connected and therefore have at least $|C_k| - 1$ edges. Then the sum $d_1+d_2+...+d_n = 2(n-1) - 2(m - 1) < 2(n-1)$. We see that $m = 1$ and graph is connected. It remains to see that connected graph with $n$ vertices has at least $n-1$ edges, being exactly $n-1$ edges only for trees.