4
$\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?

  • 0
    not as far as I know. I just took a pen and paper, and searched naively.2011-04-05

5 Answers 5

3

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.

2

(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

  • 2
    for c$a$se (c) There can not be a vertex with degree less than $2$. Let me expl$a$in this. There're **two vertices with degree 4** (i.e have edges from all remaining vertices). So, each other verte$x$ should h$a$ve **at least** two edges incident on them (from the above two vertices with degree). So there can not be a verte$x$ with degree 1. I think I'm cle$a$r. Answer is **NO**.2011-04-05
1

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.

1

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.

0

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.