Let $G$ be a graph on $n$ vertices. $G$ is allowed to have multiple edges but no loops. The degree sequence of $G$ is the tuple $(d_1,d_2,\ldots,d_n)$ with $d_1\geq d_2 \geq\cdots\geq d_n\geq 0$ obtained (inductively) as follows: $d_1$ is the highest degree of a vertex; $(d_2,\ldots,d_n)$ is the highest degree sequence in lexicographic order of a graph obtained by deleting a vertex of degree $d_1$ and its incident edges from $G$.

A tuple $D=(d_1,d_2,\ldots,d_n)$ is called *graphic* if there exist a graph with $n$ vertices, with possible multiple edges but no loops such that its degree sequence is $D$.

It is easy to show that $d_n=0$ for any graphic tuple. But of course there are other necessary conditions.

For instance $(2,2,0,0)$ is graphic with $G=(V,E)$, $V=\{1,2,3,4\}$, $E=\{[1−2],[1−2],[3−4],[3−4]\}$ whereas $(4,2,2,0)$ is not (there is no graph with $4$ vertices and with this degree sequence). However $(4,2,2,0,0)$ becomes graphic once the extra $0$ (corresponding to an extra vertex) is added. The example in this case is $V=\{1,2,3,4,5\}$, $E=\{[1−2],[1−2],[1−3],[1−3],[2−3],[2−3],[4−5],[4−5]\}$.

My question is the following: Is there a complete description of graphic tuples? For simple graphs this seems awfully close in flavour to the Erdös-Gallai Theorem. I was, however, not able to find a good reference online.

1more comment