Problem:
Prove that if $(d_1,d_2,\dots,d_n)$ where $d_1\ge d_2\ge…\ge d_n\ge 0$ is the degree sequence of a graph (NOT necessarily simple) if and only if $\sum_{i=1}^n d_i$ is even.
Answer:
Part $(\Rightarrow)$: It's trivial because each edge counts two times. So, $\sum_{i=1}^n d_i$ is even.
Part $(\Leftarrow)$: I tried to use induction on $n$, but I am not sure how to pass the induction step. Because Induction in graph theory needs special attention. If we want to use it, we should prove that our induction step contains all possibilities, and includes all $n + 1$ vertices.
So. I want a true answer in the induction step. Please help.
Best Answer
$\Longrightarrow$ is easy, as you say in your own answer. It's essentially the handshaking lemma.
$\Longleftarrow$ Draw all the vertices, and label them with their respective $d_i$ (these labels will represent how many more edges each node has room for). Now pick two nodes whose labels are strictly positive and draw an edge between them, and subtract 1 from each of their labels. Keep doing this until you can't anymore.
This process will necessarily end eventually (as the sum of all labels decreases by 2 each time and cannot get negative). It can only end because at most one non-zero node is left. If there are none left, you're done. If there is one non-zero node left, it must have an even label. Draw loops on that node (subtracting 2 from the label each time) until the label reaches 0.
Alternatively, you could draw loops on all the vertices until their labels are either 1 or 0. There must be an even number of 1's. Pair them up, and draw an edge in each pair.