Is there a known (efficient) algorithm to construct a non-connected graph with a given degree sequence (if it exists)?

### Examples

The sequence $\{3, 2, 2, 2, 2, 2, 1\}$ has both connected and non-connected realizations as simple graphs:

All non-connected realizations of this sequence are isomorphic to the graph shown above. The algorithm should construct such a graph.

All realizations of the sequence $\{3, 3, 1, 1, 1, 1\}$ are connected (it's a forcibly connected sequence) and isomorphic to:

The algorithm should either fail on this sequence, or construct a connected graph like the one above.

To help with experimentation, the following is an exhaustive list of degree sequences of size $\le 7$ that have both connected and non-connected realizations:

```
{2, 2, 2, 1, 1}
{{3, 2, 2, 1, 1, 1}, {2, 2, 2, 2, 1, 1}, {3, 3, 2, 2, 1, 1},
{2, 2, 2, 2, 2, 2}, {3, 3, 3, 3, 1, 1}}
{{4, 2, 2, 1, 1, 1, 1}, {3, 3, 2, 1, 1, 1, 1}, {4, 3, 2, 2, 1, 1, 1},
{4, 4, 2, 2, 2, 1, 1}, {3, 2, 2, 2, 1, 1, 1}, {4, 2, 2, 2, 2, 1, 1},
{2, 2, 2, 2, 2, 1, 1}, {3, 2, 2, 2, 2, 2, 1}, {3, 3, 2, 2, 2, 1, 1},
{3, 3, 3, 2, 1, 1, 1}, {4, 3, 3, 2, 2, 1, 1}, {4, 3, 3, 3, 1, 1, 1},
{4, 4, 3, 3, 2, 1, 1}, {2, 2, 2, 2, 2, 2, 2}, {3, 3, 2, 2, 2, 2, 2},
{3, 3, 3, 3, 2, 1, 1}, {4, 3, 3, 3, 3, 1, 1}, {4, 4, 4, 3, 3, 1, 1},
{3, 3, 3, 3, 2, 2, 2}, {4, 4, 4, 4, 4, 1, 1}}
```

Other interesting sequences: `{4, 4, 4, 3, 3, 3, 3, 2, 2}`

and `{4, 4, 4, 3, 3, 3, 2, 2, 1}`

. Both of these have a single non-connected realization (ignoring isomorphic duplicates) and none of the components of these realizations are cliques.

farfrom a systematic way (i.e. an algorithm). Once you create a clique, it's not even clear if the remaining degrees can be wired up to form a simple graph (and deciding this is a highly non-trivial problem). $\endgroup$ – Szabolcs Horvát May 12 at 16:42