[DaCapoo]

I have not looked over the Havel-Hakimi algorithm yet, but here's the best way I've found to solve these (with 100% success rate so far)

1. Pick the node with the highest degree 2. Make all the connections for that node until it has a value of zero by connecting it with the highest-value node that it isn't already connected to

For example, in this scenario: http://i.imgur.com/O8MlWzz.png

The way that I see it is that since the highest-degree node needs to make X number of connections, ensure it can make all of those connections before worrying about anything else. In this case, that means start by connecting the 4 to the next highest value node - the 3, then the 2, then the other 2, then the 1.

This leaves the following situation: http://i.imgur.com/9vZjafr.png

It's kind of easy to see where it goes from there. Sure this is a simple example, but as I said it's worked 100% of the time I've tried it.

[nanofortnight]

The above algorithm was proven to work for all degree sequences by Václav in 1955: https://eudml.org/doc/19050 (Non-English)

[cschmidt]

For the curious this Václav Havel

http://en.wikipedia.org/wiki/V._J._Havel

is not the better known Czech politician of the same name

http://en.wikipedia.org/wiki/V%C3%A1clav_Havel

[MichaelAza]

My intuition on this was similar - Pick the highest degree node and connect it to a node of the same degree if available or to one with the next-highest degree, preferring nodes with less connections over those with more. Repeat.

Worked for me so far, and I'm about 6 levels in with the largest node being 8.

[sfenu]

That's pretty much the Havel-Hakimi algorithm