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?

  • $\begingroup$ You correctly deduced that the graph cannot be simple. I'm no expert, but often when you allow your graphs to have loops, you also allow double edges (=two edges from A to B)... $\endgroup$ Mar 30 '12 at 7:14
  • $\begingroup$ Yes, I could have also drawn double edges instead of loops on the 3 vertices connected in a triangle. Any other ideas for solutions? $\endgroup$ Mar 30 '12 at 7:33

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.

  • $\begingroup$ I'm pretty much a novice in graph theory, could you explain a bit more in depth? $\endgroup$ Mar 30 '12 at 10:40
  • $\begingroup$ @RobertS.Barnes: Which part? $\endgroup$
    – Aryabhata
    Mar 30 '12 at 14:34
  • $\begingroup$ The Havel-Hakimi Theorem. I looked over the link, but I'm not sure what the algorithm is or it's consequences. $\endgroup$ Mar 30 '12 at 15:08
  • $\begingroup$ @RobertS.Barnes: The theorem gives you a way of transforming a giving degree sequence, into another sequence, in which you reduce the maximum degree (and possibly the number of nodes) such that the original sequence is graphical if and only if the transformed sequence is graphical. So if you keep transforming, you should end up with all $0$ ultimately. $\endgroup$
    – Aryabhata
    Mar 30 '12 at 15:36
  • $\begingroup$ Havel-Hakimi is for simple graphs, you wrote this, but OP asked for general graphs. Also adding loops is simplest possible way to do this, and OP mentioned this in his question, and seems he looks for more elegant way. $\endgroup$
    – Saeed
    Mar 30 '12 at 21:54

I will assume that loops and multiple edges are not allowed.

Since you have one vertex of degree 0, the graph would consist of one isolated vertex and the remaining vertices would form a graph with degree sequence $(2,2,4,4,4)$.

Now you have 5 vertices and 3 of them have degree 4, so these 3 vertices must be connected to all remaining 4 degrees. This implies that each vertex of this 5-vertex subgraph must have degree at least 3 (it is adjacent at least to the 3 vertices having degree 4). This is a contradiction.

  • $\begingroup$ They are allowed. $\endgroup$ Mar 30 '12 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.