Degree sequence of connected graphs

Note that there are two notions here which should be distinguished: potentially and forcibly realizable sequences.

Let $d=(d_1,\ d_2,\ \cdots,\ d_n)$ be a degree sequence, increasingly ordered $$d_1 \le d_2 \le \cdots \le d_n$$

We say that $G$ is a realization of $d$ if the degree sequence of $G$ is equal to $d$.

We say that $d$ is forcibly connected if every realization of $d$ is connected.

We say that $d$ is potentially connected if there exists a realization of $d$ which is connected.

Analogous definitions hold for any property $P$ of graphs, in which we say that a sequence $d$ is potentially/forcibly $P$-realizable if some/every realization of $d$ satisfies $P$. There are some beautiful results related to such sequences. Regarding connectivity, here are some of the basic results.

Theorem 1 (Bondy and Boesch): Let $d=(d_1,\ \cdots,\ d_n)$ be a degree sequence. Let $k$ be an integer such that $1\le k \le n-1$. If $$d_i \le i + k - 2 \implies d_{n-k+1} \ge n-i$$ for $1 \le i \le \left\lfloor \frac{n-k+1}{2}\right\rfloor$, then $d$ is forcibly $k$-connected.

Theorem 2 (Bauer, Hakimi, Kahl, Schmeichel): Let $d=(d_1,\ \cdots,\ d_n)$ be a degree sequence. Let $\lambda \ge 1$ be an integer. If $d_1 \ge \lambda$ and $$d_{i-\lambda+1} \le i - 1 \land d_i \le i +\lambda -2 \implies d_n \ge n-i+\lambda-1$$ for $\lambda+1 \le i \le \left\lfloor\frac{n}{2}\right\rfloor$, then $d$ is forcibly $\lambda$-edge-connected.

Theorem 3: Let $d = (d_1,\ \cdots,\ d_n)$ be a degree sequence. Then $d$ is potentially connected if and only if $d_1 \ge 1$ and $$\sum_{i=1}^nd_i \ge 2(n-1)$$

Theorem 4 (Edmonds): Let $d = (d_1,\ \cdots,\ d_n)$ be a degree sequence. Then $d$ is potentially $\lambda$-edge-connected ($\lambda \ge 2$) if and only if $d_1 \ge \lambda$.

Theorem 5 (Wang & Kleitman): Let $d = (d_1,\ \cdots,\ d_n)$ be a degree sequence. Then $d$ is potentially $k$-connected ($k\ge 2$) if and only if $d_1 \ge k$ and $$\frac{1}{2}\sum_{i=1}^n d_i - \sum_{i=n-k}^n d_i + \frac{(k-1)(k-2)}{2} \ge n-k$$

There is also an interesting result regarding degree sets, i.e. the multiplicities of the terms are not specified.

Theorem 6 (Kapoor, Polimeni & Wall): Let $S=\{s_1,\ \cdots,\ s_k\}$ be a set of positive integers. Then $S$ is realizable as the degree set of a connected graph. Moreover, we may take the order of the graph to be $M+1$ where $M$ is the largest member of $S$.

References (by theorem number):

1 and 2: Bauer, Hakimi, Kahl, Schmeichel. Sufficient Degree Conditions for $k$-Edge-Connectedness of a Graph.

3: Berge, Graphs and Hypergraphs. The result is not too difficult to prove using induction. There are quite a few other interesting results given in Berge's book. Especially relevant are sections of chapters 6 and 9.

4: Edmonds, Existence of $k$-edge-connected ordinary graphs with prescribed degrees.

5: Wang, Kleitman. On the existence of N-connected graphs with prescribed degrees ($n \ge 2$).

6: Kapoor, Polimeni, Wall. Degree sets for graphs, Fund. Math. 95 (1977) 189–194.