3
$\begingroup$

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?

  • 0
    Yes, I could have also drawn double edges instead of loops on the 3 vertices connected in a triangle. Any other ideas for solutions?2012-03-30

2 Answers 2

5

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.

  • 0
    @RobertS.Barnes: For connectedness you have another set of necessary and sufficient condition (as detailed in the answer to the question I linked). What part of Havel-Hakimi theorem are you having trouble with? The notation?2012-04-01
3

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.

  • 0
    They are allowed.2012-03-30