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.

I know that simple graph has no parellel edges and loops. My question is that I have to draw the graph on six vertices with degree sequence $(3,3,5,5,5,5)$. I draw the the graph with the given degree sequence and everytime I got the graph which is not simple. Does there exist a simple graph with these degree sequence? If no why?

share|improve this question
    
Do you know the Havel-Hakimi Theorem? –  EuYu Sep 18 '12 at 18:14
    
No! Can you please state this theorem! –  Kns Sep 18 '12 at 18:17

2 Answers 2

up vote 6 down vote accepted

No fancy theoretical machinery is required.

Call the vertices $v_1,v_2,v_3,v_4,v_5$, and $v_6$. Let $v_1,v_2,v_3$, and $v_4$ be the vertices of degree $5$. There are only six vertices, so each of these vertices must be connected by an edge to every other vertex in the graph. For instance, $v_2$ must be connected to $v_1,v_3,v_4,v_5$, and $v_6$. This means that $v_5$ and $v_6$ are both connected to each of the vertices $v_1,v_2,v_3$, and $v_4$ and must therefore have degree at least $4$: the degree sequence $(3,3,5,5,5,5)$ is impossible for a simple graph.

If you’d like to explore further, this kind of reasoning leads to the easy half of the Erdős-Gallai theorem, which gives a simple computational criterion for whether a sequence is the degree sequence of some simple graph. This kind of reasoning shows that a sequence that fails the criterion cannot possibly be a degree sequence; proving that every sequence that satisfies it really is the degree sequence of some simple graph is harder. See also the comments here.

share|improve this answer

By the Havel-Hakimi Theorem, a descending degree sequence $\{a_1, \cdots ,\ a_k\}$ is graphical if and only if $a_1 \le k-1$ and $\{a_2 - 1, \cdots, a_{a_1+1}-1, a_{a_1 +2}, \cdots, a_k\}$ is graphical.

Applying the theorem to your case, we have $$\{5,5,5,5,3,3\} \iff \{4,4,4,2,2\}\iff\{3,3,1,1\}\iff\{2,0,0\}$$ The latter graph is evidently impossible.

share|improve this answer
    
Evidently not. $\{1,1,1,1\}$ is the degree sequence of two disjoint $K_2$s. However, it is impossible for the sequence as originally stated. –  Rick Decker Sep 18 '12 at 19:46
    
@RickDecker Sorry about that, I must've mistyped the sequence in the middle and started using it. It is fixed now. –  EuYu Sep 18 '12 at 20:28
    
A minor point, but if you edit a post of yours it's a good idea to indicate the edit as part of your post. Otherwise someone new to this thread might be confused by the existing comments (as here, for example). –  Rick Decker Sep 18 '12 at 23:38

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.