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.

Havel-Hakimi Theorem: A sequence s: $d_1, d_2, \ldots, d_n$ of non-negative integers with $\Delta = d_1 \geq d_2 \geq \ldots \geq d_n$ and $\Delta \geq 1$, is graphical if and only if the sequence $$s_1: d_2 - 1, d_3 - 1, \ldots d_{\Delta + 1} - 1, d_{\Delta + 2}, \ldots, d_n$$ is graphical.
Havel-Hakimi theorem provides an algorithm for determining whether a given finite sequence of non-negative integers is graphical. If, upon repeated application of Theorem 1, we arrive at a sequence, where every term of which 0, then the original sequence is graphical. On the other hand, if we arrive a sequence containing a negative integer, then the given sequence is not graphical.

I tried several sequences and realized, the sequence is not graphical if it fails Havel-Hakimi's theorem. However, it doesn't always work for connected graph. For instance, the sequence: $$ 3, 3, 1, 1, 1, 1, 1, 1$$ can be processed by Havel-Hakimi's algorithm as follows:

3, 3, 1, 1, 1, 1, 1, 1
2, 0, 0, 1, 1, 1, 1
2, 1, 1, 1, 1, 0, 0
0, 0, 1, 1, 0, 0
1, 1, 0, 0, 0, 0
0, 0, 0, 0, 0

But it can't be graphed as a connected component. On the other hand, the sequence: $$5, 4, 3, 2, 2, 2, 2, 2$$ also satisfies the Havel-Hakimi's algorithm, but can be graphed as follows:

enter image description here

So my question is, what other conditions need to be added so that Havel-Hakimi's algorithm work for connected graph? Thank you.

share|improve this question
    
It seems that some results in this direction are mentioned in Melnikov: Exercises in graph theory, namely Theorem 8.2.2 on p.126 could be of interest. (Or at least it could suggest some keywords for which to work. As stated on the book only says when a sequence is connected graphical sequence, it does not mention any algorithm.) –  Martin Sleziak Sep 2 '11 at 7:54
    
Ok, after a closer look, the above theorem only speaks about k-connected graphs for $k\ge 2$, but Exercise 8.2.8 on p. 127 is about potentially connected graphical sequences. Another reference for the same result is given here. –  Martin Sleziak Sep 2 '11 at 8:15
    
This answer mentions several results on degree sequences of connected graphs: math.stackexchange.com/questions/732303/… –  Martin Sleziak Apr 3 at 10:25

1 Answer 1

up vote 9 down vote accepted

Maybe someone will come up with a better answer or explain the details, but I've decided to make my second comment into an answer.

After little googling I found the following:

Exercise 8.2.8 on p. 127 in Melnikov: Exercises in graph theory:

Prove that a proper graphical n-sequence without zeroes is potentially connected if and only $\sum_{i=1}^n d_i \ge 2(n-1)$.

Page 117:

A sequence $d$ is called $d$-graphical if there exists a graph whose degree sequence is $d$. Such graph is called a realization of the sequence $d$.

A non-increasing $n$-sequence $d$ is called proper if its sum is even and $d_1\le n-1$

A potentially graphical sequence is a graph sequence that has a realization via connected graph.

Page 286:

Hint: The sufficiency may be proved by induction over $n$. The inductive step may be based on the Havel-Hakimi theorem.

Havel-Hakimi theorem is in this book formulated as follows:

For a proper $n$-sequence, $n>1$, the derived sequence $d^i$, $1\le i\le n$ is defined as follows. The element $d_i$ is deleted from $d$ and the first $d_i$ remaining elements are decreased by 1.

Theorem 8.1.3 (V. Havel, S. Hakimi) A proper $n$-sequence $d\ne(0^n)$ is graphical if and only if every derived sequence $d^i$, $1\le i\le n$, is graphical.

This paper mentions that:

In [4] it is claimed that for a sequence to be graphical and potentially connected it is necessary and sufficient that $$\sum_{i=1}^k d_i \le k(k-1) + \sum_{i=k+1}^n \min(k,d_i)$$ holds and the sum of degrees is at least $2(n-1)$, i.e., there are at least enough degrees to produce a spanning tree. However, no algorithm is given other than to produce a spanning tree and then use the Havil-Hakimi algorithm on the residual graph.

[4] M. Mihail and N. K. Vishnoi. On Generating Graphs with Prescribed Vertex Degrees for Complex Network Modelling. In ARACNE 2002, pages 1-12, 2002.

(The above condition is the condition from Erdős-Gallai theorem.)

A modification of Havel-Hakimi algorithm to obtain connected graph is described in the paper Fabien Viger and Matthieu Latapy: Efficient and simple generation of random simple connected graphs with prescribed degree sequence. However, this paper does not mention any conditions for the existence of a connected graph.

EDIT

Finally I found a book that gives also a complete proof. The proof is different from the one suggested in the hint in Melnikov's book. (I spent some time thinking about this hint and I was not able to complete the solution. I am not especially experienced with graph theory, but I suspect the author of the book might make a mistake there. Or - more probably - I misunderstood his hint.) The basic idea of the proof given in this book is to first construct a graph from the degree sequence and if it is not connected to swap edges several times until it becomes connected.

Claude Berge: Graphs and Hypergraphs, Theorem 9, p. 117-118:

Let $d_1\ge d_2 \ge \ldots \ge d_n$ be a sequence of integers, $n\ge 2$. A necessary and sufficient condition for existence of a simple connected graph $G$ with degrees $d_G(x_i)=d_i$ is that $$\begin{gather*} d_n \ge 1\\ \sum_{i=1}^n d_i \ge 2(n-1)\\ \sum_{i=1}^n d_i\text{ is even }\\ \sum_{i=1}^k d_i \le \sum_{i=1}^k \overline d_i \end{gather*}$$

Only the conditions $d_n\ge 1$ and $\sum_{i=1}^n d_i \ge 2(n-1)$ is added here to the conditions from the theorem which characterizes degree sequences for simple graphs. It is just a different formulation of Erdős-Gallai theorem.

The meaning of $\overline d_i$ (which the author calls corrected conjugate of the sequence $d_i$) is explained on page 111.

share|improve this answer
    
Thanks a lot for your answer ;) –  Chan Sep 3 '11 at 1:27
    
You're welcome @Chan. I did more searching than actual thinking about the given problem, so you have to do more work - to have a look at the references and fill in the details. I wonder whether you were able to finish the proof based on Melnikov's hint - I somehow got stuck on that one.\\BTW I am not sure whether this answers your question. Did you want any algorithm to produce connected graph from a degree sequence or are you more interested in the question when the usual Havel-Hakimi algorithm produces a connected graph? –  Martin Sleziak Sep 3 '11 at 7:09
    
Thanks for the additional proof. In fact, I already proved that any graphical & connected graph must have $\sum_{i=1}{n} d_i \geq 2(n-1)$ by induction on $n$. Your answer gave more than I expected ;), but yes it did answer my question. On the other hand, what I want to achieve is a condition on the Havel-Hakimi algorithm so that I implement an algorithm to test a sequence of degrees for graphical-connectivity. –  Chan Sep 3 '11 at 18:22

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.