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

Question

I'm trying to make a list of ways to tell if a given degree sequence is impossible. For example $3,1,1$ is not possible because there are only 3 vertices in total so one can't have degree 3.

The list so far

• vertices has degree equal to or larger than number of vertices
• sum of degrees is odd
• for n vertices if one has degree n-1 and another has degree 0
• for n vertices the sum of the degrees cannot be greater than $n(n-1)$ because this would be have more edges than a complete graph

Answer 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$.