Constructing a graph from a degree sequence

Solution 1:

If you have some requirements like planarity or connectedness, then you are left with trial and error. However, if you would like any simple graph with the given degree sequence, then you can do a simple algorithm:

• Sort the degrees descending.
• Connect the highest degree $d$ to the next $d$ vertices, e.g. $$(4,3,2,1,1,1) \leadsto (3-1,2-1,1-1,1-1,1) = (2,1,1).$$
• Iterate until finished.

The idea behind it is rather simple, if you want the full proof, then you can find it here (Václav Havel, 1955, non-English). Some info is also available at MathWorld.

I hope this helps $\ddot\smile$