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