# Is a graph simple, given the number of vertices and the degree sequence?

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?

-
The answer to a, and for d are in fact yes. – yaakov Apr 5 '11 at 16:46
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. – André Nicolas Apr 5 '11 at 16:50
@yaakov How do I know this? Is there a given property that tells me this? – Garee Apr 5 '11 at 16:52
not as far as I know. I just took a pen and paper, and searched naively. – yaakov Apr 5 '11 at 17:42

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.

-

(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

-
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. – Amit L Apr 5 '11 at 17:53

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.

-

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.

-