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
    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)...2012-03-30
  • 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
    I'm pretty much a novice in graph theory, could you explain a bit more in depth?2012-03-30
  • 0
    @RobertS.Barnes: Which part?2012-03-30
  • 0
    The Havel-Hakimi Theorem. I looked over the link, but I'm not sure what the algorithm is or it's consequences.2012-03-30
  • 0
    @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.2012-03-30
  • 0
    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.2012-03-30
  • 0
    @Saeed: For general graphs which allows loops and multiple edges, you don't need any theorems to prove existence. I stated that clearly in my answer and also mentioned why it is so, and IMO that is quite uninteresting as we can trivially construct at least one graph as long as the number of odd degrees is even (which is a necessary condition).2012-03-30
  • 0
    @Saeed: I don't understand your point.2012-03-30
  • 0
    @Aryabhata, I talked in first part of my comment about Havel-Hakimi, IMO, it's not useful here (and there is no need to say it). And in second part, I mean creating graph by adding loops is not interesting, and OP previously found this way.2012-03-30
  • 0
    @Saeed: You seem to be reading too much into the question. Where did OP say he is not interested in simple graphs or graphs with loops? The fact that he did end up with a graph with loops and is asking for a better _way_ (note: not better _graph_), he definitely is interested in graphs with loops. Havel Hakimi can be used for simple graphs. OP could easily have misunderstood the problem he is trying to solve and the problem is actually looking for simple graphs (which is typical, if he is taking a basic course on graph theory).2012-03-30
  • 0
    You can read the last line of question: "Is this the only solution And ....". Also I'm agree with that, problem seems to be asked for simple graphs and OP misunderstood this.2012-03-30
  • 0
    @Saeed: Yes, OP could be asking for a different graph (note: not necessarily 'not simple' or 'not with loops'), and if you read carefully, my answer does answer that implicitly. The graph I describe in the latter part of my answer describes a different graph from what OP got.2012-03-30
  • 0
    The question is to determine what kind of graph exists given a set of vertices and their degrees: simple and connected, simple but not connected, connected but not simple. Havel-Hakimi looks very interesting, I just would like a step by step description of the algorithm and it's necessary conditions as I found the linked post a bit hard to follow.2012-04-01
  • 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