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?

  • $\begingroup$ Do you know the Havel-Hakimi Theorem? $\endgroup$
    – EuYu
    Sep 18, 2012 at 18:14
  • $\begingroup$ No! Can you please state this theorem! $\endgroup$
    – Kns
    Sep 18, 2012 at 18:17

2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$ Sep 18, 2012 at 19:46
  • $\begingroup$ @RickDecker Sorry about that, I must've mistyped the sequence in the middle and started using it. It is fixed now. $\endgroup$
    – EuYu
    Sep 18, 2012 at 20:28
  • $\begingroup$ 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). $\endgroup$ Sep 18, 2012 at 23:38

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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .