Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

4 Answers 4

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.

share|improve this answer

(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

share|improve this answer
1  
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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.