Problem:
For a graph $G$ with vertices $u_1, u_2, . . . , u_n,$ the sequence
$(deg(u_1), deg(u_2), . . . , deg(u_n))$ is called the degree sequence of $G$. Show that a sequence $(d_1, d_2, . . . , d_n)$ of non-negative
integers is a degree sequence of a (not necessarily simple) graph if and only if
$\sum_i^{n}d_i$ is even.. (Hint: use induction on $n$.) I wish to solve the backwards direction.
My idea is to take a subset of the graph with $n$ elements that sums to an even number and then use the induction hypothesis on this subgraph, and then treat the $n+1$'th element not in this subgraph with a number of loops since it must have even degree.
Attempt:
If I have a graph of only $1$ vertex, and its degree is even say $2m$ for some $m \in \Bbb N$ then I can construct a graph with one vertex and $m$ loops.
Now suppose that a degree sequence $\sum_i^{n}d_i$ is even and that we can construct a graph with this degree sequence, then if $\sum_{i}^{n+1}d_{i} =2j$ for some $j \in \Bbb N$, then how can I show that there must be a graph that satisfies this degree sequence using the induction hypothesis?
Best Answer
Note that the inductive hypothesis is that EVERY sequence of nonnegative integers of length $n$ with even sum is the degree sequence of a graph.
Now suppose that $(d_1,\dots,d_n,d_{n+1})$ is a sequence of nonnegative integers such that $d_1+\cdots+d_n+d_{n+1}$ is even. We consider two cases.
Case 1. $d_{n+1}$ is odd.
Then $d_1+\cdots+d_n$ is odd, and we can choose $k\in\{1,\dots,n\}$ so that $d_k$ is odd. Define $$d'_i=\begin{cases} d_i\ \ \ \ \ \ \ \text{ if }i\ne k,\\ d_i-1\text{ if }i=k.\\ \end{cases}$$ Then $(d'_1,\dots,d'_n)$ is a sequence of nonnegative integers with even sum, so it's the degree sequence of some graph $G$ on the vertex set $u_1,\dots,u_n.$ Add a new vertex $u_{n+1},$ an edge joining $u_{n+1}$ to $u_k,$ and $(d_{n+1}-1)/2$ loops joining $u_{n+1}$ to itself; the resulting graph has degree sequence $(u_1,\dots,u_n,u_{n+1}).$
Case 2. $d_{n+1}$ is even.
This is like Case 1 but easier; details left to the reader.