Determining connectivity of a graph.

Question

I recently came across the Havel-Hakimi Theorem/Algorithm which tells us whether a simple graph with a given degree sequence can exist. This however does not tell us whether the graph is connected or not.

Is there any such procedure that can tell us about the above criterion which does not require drawing the graph itself, i.e. by using its degree sequence?

Answer 1

In order for a given sequence $d_1, d_2, \dots, d_n$ to be the degree sequence of a connected graph, we need three things:

1. It's graphic: that is, it's the degree sequence of some (simple) graph. This can be checked with the Havel-Hakimi algorithm.
2. $d_1 + d_2 + \dots + d_n \ge 2(n-1)$; this tells us that there are at least $n-1$ edges, the minimum needed for the graph to be connected.
3. $\min\{d_1, d_2, \dots, d_n\} \ge 1$; this tells us that there are no isolated vertices.

These three conditions are also clearly necessary, and turn out to also be sufficient.

To prove that, we start with any graph that has this degree sequence. If it's not connected, we will reduce the number of connected components until it is.

If a graph with at least $n-1$ edges has no cycles, then it must be connected (and a tree). So if our graph is not connected, it has a cycle. Let $vw$ be any edge of the cycle; let $xy$ be any edge that's not in the same component as the cycle. (The other components can't be isolated vertices, by condition 3, so they must contain at least one edge.)

Delete edges $vw$ and $xy$, and replace them by edges $vx$ and $wy$. (These edges weren't there before, because their endpoints were in different connected components.) This operation doesn't change any degrees; however, it reduces the number of connected components by $1$. Before, $v,w$ were in one connected component and $x,y$ were in another. Now, $v$ and $w$ are still connected (since $vw$ part of a cycle); $x$ and $y$ are part of that component now, and so was everything connected to $x$ or to $y$.

If we keep doing this, eventually, we'll end up with a connected graph.