Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 12 down vote accepted

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.

share|improve this answer
    
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

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

share|improve this answer
    
Thanks a lot. I wonder what could be the condition to verify a connected graph is drawable? –  Chan Sep 1 '11 at 5:35
1  
You may be interested in this paper. –  Shahab Sep 1 '11 at 6:24
    
Nice paper, thanks a lot. –  Chan Sep 2 '11 at 5:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.