List of ways to tell if degree sequence is impossible for a simple graph

Solution 1:

The Erdős–Gallai theorem completely characterizes the possible degree sequences for simple graphs.

It is stated by Wikipedia as:

A sequence of non-negative integers $d_1\geq\cdots\geq d_n$ can be represented as the degree sequence of a finite simple graph on $n$ vertices if and only if $d_1+\cdots+d_n$ is even and $$ \sum^{k}_{i=1}d_i~\leq~ k(k-1)+ \sum^n_{i=k+1} \min(d_i,k)$$ holds for $1\leq k\leq n$.

Solution 2:

Three is Havel–Hakimi algorithm It is stated by Wikipedia as:

The algorithm The algorithm is based on the following theorem. Let $$S=(d_{1},\dots ,d_{n})$$ be a finite list of nonnegative integers that is nonincreasing. List S is graphic if and only if the finite list $$S'=(d_{2}-1,d_{3}-1,\dots ,d_((d_{1}+1))-1,d_((d_{1}+2)),\dots ,d_{n})$$ has nonnegative integers and is graphic. If the given list S graphic then the theorem will be applied at most $n-1$ times setting in each further step $$S:=S'$$. Note that it can be necessary to sort this list again. This process ends when the whole list S' consists of zeros. In each step of the algorithm one constructs the edges of a graph with vertices $$v_{1},\cdots ,v_{n}$$, i.e. if it is possible to reduce the list $S$ to $S'$, then we add edges $$\{v_{1},v_{2}\},\{v_{1},v_{3}\},\cdots ,\{v_{1},v_((d_{1}+1))\}$$. When the list S cannot be reduced to a list S' of nonnegative integers in any step of this approach, the theorem proves that the list S from the beginning is not graphic.

see also
What condition need to be imposed on Havel-Hakimi theorem to check for connected graph?

Solution 3:

The most general version is the Erdos-Gallai theorem, referred to in this MathOverflow post.