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.

Suppose you have a given degree sequence $(d_1,d_2,\dots,d_n)$, where $d_i$ is even for every $i$. Does there exist a general graph with this degree sequence?

I say yes, the easiest way is to take any isolated graph of $n$ vertices, $\{v_1,\dots,v_n\}$, and then at each $v_i$, put in $d_i/2$ loops, so $\deg(v_i)=d_i$ for all $i$. Is this cheating? It seems very easy, and it all hinges on the fact that graph is allowed to have multiple edges between vertices.

As a follow up question, is there some way, sufficient and/or necessary conditions to tell if a graph with a given degree sequence exists, given that the sum of the degree sequence is even? (It may not necessarily be the case that every degree may be even itself.)

share|improve this question

3 Answers 3

up vote 8 down vote accepted

Self-loops make the question rather uninteresting. If you forbid them, the answer is given by the Erdős–Gallai theorem.

share|improve this answer
    
Thanks! I agree the self-loops feel like a cop out. I'll read up on this. –  Hobbie Apr 11 '11 at 20:43

If you are looking for a simple graph, the Erdos Gallai Theorem mentioned before solves the problem. Also there is another theorem by Havel-Hakimi, which is more an algorithm (and also constructs such a graph):

$d_1 \geq d_2 \geq d_3 ... \geq d_n$ is the degree sequence of a graph if and only if

$d_2-1, d_3-1, ..., d_{d_1+1}-1, d_{d_1+2},..., d_n$ is a degree sequence.

It should be pretty clear how to construct the graph.


For general graphs:

If you allow both loops and multiple edges, any sequence of numbers with even sum is a degree sequence. To see this, split the odd vertices in pairs, add one edge for each pair and then you are left exactly with the case you covered: all the vertices have even degree.

I think that if you don't allow loops but you allow multiple edges, you can do it if and only if the sum of degrees is even AND the largest degree is less or equal to the sum of the remining vertice. The only if part should be clear, while the if part can be proven the following way: add an edge between the two highest degrees, show that the largest degree is still less or equal to the sum of the remining vertices, and do induction by the sum of the degrees.

share|improve this answer

The Erdos-Gallai Theorem not only forbids loops but multiple edges as well. One can look at degree sequence problems in settings where one wants a connected graph and multiple edges are allowed but not loops, etc. Here is a reference to a paper where there are limitations on loops and multiple edges but the are "partially" allowed: A Note on Degree Sequence of Graphs with Restrictions by F.A. Muntaner-Batle and M. Rius-Font (submitted for publication).

share|improve this answer

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.