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

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.)