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

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
• Please remove 2 from denominator in 4 th point Sep 12, 2018 at 17:32
• do you think? I'm not sure about that @Believer Jan 21, 2019 at 18:10
• @Marine Galantin, yes I am sure.Take complete graph on 4 vertices as a counter example.Also read answer by Sanjeet kumar Jan 23, 2019 at 17:19
• Well it has 6 edges? Because the edges are simple and not in both direction Jan 23, 2019 at 17:21

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