I think I'm doing something wrong in the following exercise, but I don't know what it is.
Let the degree sequence of a graph be: $\vec{d}=(d_1,d_2,\dots,d_n)$, where $d_1\ge d_2\ge…\ge d_n\ge 0$, where $d_i$ is the degree of vertex $i$ in the graph. Obviously there are $n$-vertices in the graph.
Show that there's a loopless graph with degree sequence $\vec{d}$ if and only if $\sum_{i=1}^n d_i$ is even and $d_1\leq\sum_{i=2}^n d_i$.
Part $(\Rightarrow)$: In a loopless graph, $d_1\leq m$, where $m=\frac{1}{2}(\sum_{i=1}^nd_i)$. Therefore: $d_1\leq \sum_{i=2}^nd_i$.
Part $(\Leftarrow)$: I have no idea. For example, $n=3$, I know that $d_1\leq d_2+d_3$. I can prove by example that there's a loopless graph, but not for a general case.
Best Answer
The part you are missing can be proved by induction on $\sum d_i$.
The base case $\sum d_i=0$ is realized by $n$ isolated vertices.
Assume $\sum d_i>0$, so at least $d_1\geq1$.
Case 1: $d_1=d_2+\ldots+d_n$. Then take the graph with vertices $v_1,\ldots,v_n$, and $d_i$ edges from $v_1$ to $v_i$ for all $i=2,\ldots,n$.
Case 2: $d_1<d_2+\ldots+d_n$. The difference between the two sides must be at least 2, since the total sum is even. Since $d_1\geq1$ and $d_1$ is the largest value, there must at least be two nonzero values after $d_1$. Now subtract 1 from the two lowest nonzero values and apply the induction hypothesis. In the resulting multigraph add an edge between two vertices whose degrees correspond with the values you reduced in the previous sentence.