7
$\begingroup$

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.

  • 0
    @Shahab: Thank you. However, $G$ must be connected, and undirected.2011-09-01

2 Answers 2

13

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.

  • 0
    @Chan The algorithm also works on both components separately. You are right though, even if you have a disconnected graph the algorithm works both on the components individually and on the entire sequence.2011-09-02
3

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

  • 0
    Nice paper, thanks a lot.2011-09-02