degree sequence for a graph

Question

I have to draw a connected (undirected) graph with 6, 5, 3, 3, 3, 3, 3, 2, 2 degree sequence. Can anybody tell me is there any specific approach for this or I have to try all hit and trial method for this ?

Answer 1

If you want a systematic approach, I'd recommend the Havel-Hakimi algorithm. Start out with all the vertices you want labeled with their desired degrees. Then choose the vertex that needs the most edges (say $d$), and connect it to the $d$ other vertices that need the most edges. Everytime a vertex receives an incident edge, lower the desired degree by one. That first vertex that initially needed $d$ edges will now have a $0$ desired degree, since it has all its edges. You can then do the same thing over and over with the remaining vertices until each vertex has a desired degree of zero.

Play the game here to get an idea of how it works: http://jacquerie.github.io/hh/