6
$\begingroup$

Does there exist a simple graph with five vertices of the following degrees?

(a) 3,3,3,3,2

I know that the answer is no, however I do not know how to explain this.

(b) 1,2,3,4,3

No, as the sum of the degrees of an undirected graph is even.

(c) 1,2,3,4,4

Again, I believe the answer is no however I don't know the rule to explain why.

(d) 2,2,2,1,1

Same as above.

What method should I use to work out whether a graph is simple, given the number of vertices and the degree sequence?

$\endgroup$
4
  • $\begingroup$ The answer to a, and for d are in fact yes. $\endgroup$
    – yaakov
    Apr 5 '11 at 16:46
  • $\begingroup$ Why, for example, do you believe that 2,2,2,1,1 is not possible? Simple sketching should show that it is possible, in more than one way. $\endgroup$ Apr 5 '11 at 16:50
  • $\begingroup$ @yaakov How do I know this? Is there a given property that tells me this? $\endgroup$
    – Garee
    Apr 5 '11 at 16:52
  • $\begingroup$ not as far as I know. I just took a pen and paper, and searched naively. $\endgroup$
    – yaakov
    Apr 5 '11 at 17:42
4
$\begingroup$

The answer to both a, and d, is that in fact such graphs exit. It is not hard to find them. The answer for c is that there cannot be such a graph - since there are 2 vertices with degree 4, they must be connected to all other vertices. Therefore, the vertex with degree one, is an impossibility.

$\endgroup$
3
$\begingroup$

(a) 3,3,3,3,2 - YES! Graph Justifies claim

(b)1,2,3,4,3 - NO -Follows from the Handshaking Lemma

(c)1,2,3,4,4 - ANYBODY? (has no problem by Handshaking Lemma)

(d)2,2,2,1,1 - YES! Graph Justifies Claim

$\endgroup$
1
  • 3
    $\begingroup$ for case (c) There can not be a vertex with degree less than 2. Let me explain this. There're two vertices with degree 4 (i.e have edges from all remaining vertices). So, each other vertex should have at least two edges incident on them (from the above two vertices with degree). So there can not be a vertex with degree 1. I think I'm clear. Answer is NO. $\endgroup$
    – amitlan
    Apr 5 '11 at 17:53
1
$\begingroup$

See http://en.wikipedia.org/wiki/Degree_%28graph_theory%29 or google for "degree sequence". I have only seen Havel-Hakimi theorem before, but wikipedia also mentions other results.

$\endgroup$
1
$\begingroup$

a.) Apply Havel-Hakimi:

$$ \begin{align} & 3,3,3,3,2 \\ \to & 0,2,2,2,2 \\ \to & 2,2,2,2 \end{align} $$

Since the sequence $2,2,2,2$ is graphic (it is the degree sequence of $C_4$), then the original sequence is graphic.

c.) Reorder and apply Havel-Hakimi:

$$ \begin{align} & 4,4,3,2,1 \\ \to & 0,3,2,1,0 \\ \to & 3,2,1 \end{align} $$

Since the sequence $3,2,1$ is not graphic (a graph on 3 vertices can have maximum degree of 2), then the original sequence is not graphic.

d.) Apply Havel-Hakimi:

$$ \begin{align} & 2,2,2,1,1 \\ \to & 0,1,1,1,1 \\ \to & 1,1,1,1 \end{align} $$

Since the sequence $1,1,1,1$ is graphic (it is the degree sequence of $K_2+K_2$), then the original sequence is graphic.

$\endgroup$
0
$\begingroup$

You can use the Handshaking lemma and the Havel-Hakimi algorithm to solve these problems. Here is a link to a powerpoint on it.

Basically, it goes like this (using the degree sequence [3 2 2 1] as an example):

  1. If any degree is greater than or equal to the number of nodes, it is not a simple graph.
  2. Handshaking lemma: if the number of vertices with odd degrees is odd, it is not a simple graph.
  3. Order the degree sequence into descending order, like 3 2 2 1
  4. Remove the leftmost degree: 2 2 1 , and call the first degree k, so k=3 here
  5. Subtract 1 from the leftmost k degrees: 1 1 0
  6. If any of the degrees are negative, it is not a simple graph.
  7. Go back to step 3 and repeat 3-7 until we find it is not a simple graph, or all degrees are 0, or we reach another situation we know it is a simple graph (like a cycle with 2 2 2 ...).

In the case of 3 2 2 1, we would do it like this

3 2 2 1

2 2 1 <- intermediate step (4), do not apply the handshaking theorem here yet

1 1 0 <- after step 5; this is a simple graph, so we stop here and find that 3 2 2 1 is a simple graph.

(a)

So for your (a), it would be

3 3 3 3 2 <- looks good through steps 1 and 2

3 3 3 2 <- step 4

2 2 2 2 <- step 5, subtract 1 from the left 3 degrees. Now we have a cycle, which is a simple graph, so we can stop and say 3 3 3 3 2 is a simple graph. Or keep going:

2 2 2

1 1 2

1 1

0 0 <- everything is a 0 after going through the full Havel-Hakimi algo, so yes, 3 3 3 3 2 is a simple graph.

(c)

4 4 3 2 1

4 3 2 1

3 2 1 0 <- looks good after one iteration through havel-hakimi

2 1 0

1 0 -1 <- negative degrees aren't possible, so we know that 4 4 3 2 1 is not a simple graph.

(d)

you should be able to draw (d) pretty easily. 2 vertices connected as a pair, and 3 in a cycle.

$\endgroup$

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.