What condition need to be imposed on Havel-Hakimi theorem to check for connected graph?

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:

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

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.

I only learned of graphical sequences a couple hours ago, and (indepently) discovered the Havel-Hakimi solution through the game here: http://jacquerie.github.io/hh/. I really recommend playing at least a few "rounds" to see how well you understand (or learn) how Havel-Hakimi works.

My graph theory classes were a couple decades ago, so I only have an intuitive and not rigorous proof, but offer the following observation (lemma):

Two graphical sequences can be concatenated to form a new graphical sequence.

Corollary:

If a graphical sequence can be partitioned into two (or more) graphical sequences, then a non-connected graph solution exists.

The simplest non-empty graphical sequence is 1,1. You can append this to any graphical sequence to get a new graphical sequence which has a non-connected graph as solution. This does not, however, show that a connected solution does not exist.

Consider 2,2,2,1,1. This can be partitioned into 2,2,2 and 1,1, and using the "traditional" implementation of Havel-Hakimi's algorithm will yield this graph (if you consider subtracting one each time as drawing a line to a node).

However, if the numbers are rearranged thusly:

1 2 2 2 1
- 1 2 2 1
- - 1 2 1
- - - 1 1
- - - - 0

then we get a path of five nodes (a graph like: o-o-o-o-o ).

I broke the strict ordering as specified in the Havel-Hakimi theorem. Here it works, but most arbitrary re-orderings won't (play the game and see).

For your first example (3,3,1,1,1,1,1,1) there are two partitionings: 3,3,1,1,1,1|1,1 and 3,1,1,1|3,1,1,1.

Here you can see a partially constructed graph with two possible solutions, where 2,1,1 can become a separate graph, or they can be connected to the main graph. (Not the simplest example, but one that jacquerie.github.io/hh/ just generated.)

@Martin Sleziak references a paper that generates a connected realization of a degree sequence like so: 1) generate any realization using the standard Havel–Hakimi procedure 2) rewire the edges in a way that preserves the degree sequence, but makes the graph connected.

This method works, but it is rather complicated to implement.

I found a much simpler algorithm to generate a connected realization directly, and detailed it in a blog post. I will summarize the method here. For the proofs, see the blog post.

The Havel–Hakimi algorithm is often presented like this:

1. Take a node with the highest (remaining) degree. Let us denote this degree by $d$.
2. Connect it to $d$ other nodes with the highest (remaining) degrees.
3. Repeat from step 1 until all degrees are used up.

However, it is not in fact necessary to select the highest degree node in step 1. Any node can be chosen, and the theorem still stands (i.e. the algorithm builds a simple graph iff the starting sequence was graphical). In your formulation, we can work with a degree sequence $d_1, d_2 \ge \dots \ge d_n$, without the requirement that $d_1 \ge d_2$. I believe that the usual presentation chooses the highest degree node only because the algorithm will finish in fewer steps this way.

Theorem: If in step 1. we always choose the node with the smallest remaining degree, and if the starting degree sequence was graphical and potentially connected, then the algorithm will build a connected graph.

For the proof, see the blog post or preprint. For an implementation, see IGRealizeDegreeSequence in IGraph/M or igraph_realize_degree_sequence in igraph.

Thus, to summarize:

What condition need to be imposed on Havel-Hakimi theorem to check for connected graph?

You simply need to choose the smallest degree node in each step.

However, if you are not actually building a graph, only checking for graphicality, then you are better off with the Erdős-Gallai theorem. See this paper by Z. Király for a fast and practical implementation.

Whether the degree sequence is potentially connected can be verified by checking if $\sum_{i=1}^n d_i \ge 2(n-1)$, as Martin noted.