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

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.

-
If you are not restricting yourself to simple graphs, the only thing you need to check is whether the sum of the degrees is even or not. –  Shahab Sep 1 '11 at 6:17
@Shahab: Thank you. However, $G$ must be connected, and undirected. –  Chan Sep 1 '11 at 6:20

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.

-
Thanks a lot for those info. –  Chan Sep 1 '11 at 3:45
I wonder how different it will be on the sequence after applying Havel-Hakimi algorithm because my graph is connected? –  Chan Sep 1 '11 at 5:23
@Chan Both algorithms are intended to operate on connected components so the Havel-Hakimi algorithm will work perfectly on your connected graph. –  user12998 Sep 1 '11 at 15:13
Thanks a lot once again. –  Chan Sep 1 '11 at 21:04
Hi Robert Wiberg again, I've just encountered one particular sequence today and I think it won't work on connected components. For example, $3, 3, 1, 1, 1, 1, 1, 1$, it satisfied Havel-Hakimi, but when I graph it, it is not connected. –  Chan Sep 2 '11 at 5:15