6
$\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
    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.2011-09-01
  • 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
    Thanks a lot for those info.2011-09-01
  • 0
    I wonder how different it will be on the sequence after applying Havel-Hakimi algorithm because my graph is connected?2011-09-01
  • 0
    @Chan Both algorithms are intended to operate on connected components so the Havel-Hakimi algorithm will work perfectly on your connected graph.2011-09-01
  • 0
    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.2011-09-02
  • 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
    Thanks a lot. I wonder what could be the condition to verify a connected graph is drawable?2011-09-01
  • 1
    You may be interested in [this paper](http://oai.cwi.nl/oai/asset/1579/1579A.pdf).2011-09-01
  • 0
    Nice paper, thanks a lot.2011-09-02