Given a graph with 6 vertices of degrees 0 2 2 4 4 4, in what ways may it be drawn? Simple and connected or some combination of?
Obviously it can't be connected due to the vertex with degree 0, but what can I do with the remaining 5 vertices? The graph would have 8 edges since $\frac{\sum deg(v_i)}{2} = 8$.
I noticed that $K_5$ has 10 edges which means that each vertex has deg=4. You take away any edge and you end up with 2 edges having deg=3. At this point the only way to get desired set of degrees is to remove an edge between the 2 vertices having deg=3. But we already removed the only edge between them, so the graph of the remaining 5 vertices is either not simple or not connected.
So at this point I drew a graph where each vertex has a loop and 3 vertices are connected in a triangle, giving the desired set of degrees and number of edges.
Is this the only solution and is there a better way to approach the problem other than trial and error in drawing the graph?
Best Answer
You can use the Havel-Hakimi theorem (which is applicable to simple graphs).
Using that theorem your sequence $4,4,4,2,2,0$ becomes $3,3,3,1,1,0$ after one step of application. The sum of those degrees is odd, therefore no such (simple) graph exists.
If you allow for loops and multiple edges, to each vertex of even degree, you can add multiple self loops.
Since the number of vertices of odd degree must be even, you can pair them off and then add multiple self loops to each.
So, as long as the degree sequence has an even number of odd degrees (which is a necessary condition), you can find a non-simple graph (with loops) with that degree sequence, and is quite uninteresting.