How to determine if it's possible to draw a graph $G$ with a given set of vertices?

Question

Given a list of vertices associated with its degree, says: $$7, 7, 3, 3, 3, 3, 3, 1$$ Determine whether it is possible to draw a graph $G$, where $G$ is connected and un-directed.

Solution: The above graph is impossible to draw because the first two vertices will make every other vertices have degree 2.
But I realize this approach is too specific, and it's not feasible if the given list is large, let's say $n > 100$, where $n$ is the number of vertices. So my question is, if a general list of $n$ vertices is given with a degree from $1 \rightarrow n - 1$, then is there a general formula to determine whether it is possible to draw its graph? Thank you.

Answer 1

It is not enough for the sums of the degrees of the vertices to be even. A simple counterexample is 2,2,2,4.

I know of 2 common algorithms that can be used to determine whether or not a list of integers represents a valid degree sequence. They are the Erdos-Gallai Theorem and the Havel-Hakimi Theorem.

I believe that generally Havel-Hakimi is a little easier to implement and a quick google search turns up several different existing programs.

Answer 2

Have a look on the wikipedia page

In general if one allows any type of graph, then a sequence whose sum of degrees is even will have a graph, and any sequence whose sum of degrees is odd will not have a graph.

If you wish to impose extra conditions on the type of graph, then the problem appears much harder