2
$\begingroup$

When you're given a degree sequence, what is the method to draw a graph which has that degree sequence?

Consider the degree sequence $(1, 2, 2, 3, 5, 5)$. Either draw a graph with this degree sequence of prove that no such graph exists.

NB: I'm aware that no degree sequence can contain an odd number of odd numbers. Also, there is at most one edge between two vertices and there cannot be an edge from a vertex which is incident to itself.

$\endgroup$
  • 1
    $\begingroup$ Are two vertices allowed to have more than one edge beween them? $\endgroup$ – Arthur Jul 1 '19 at 12:13
  • $\begingroup$ @Arthur Nope, there is at most one edge between two vertices. $\endgroup$ – CubbyKushi Jul 1 '19 at 12:36
  • $\begingroup$ How about loops? That is can there be an edge from a vertex to itself? $\endgroup$ – paw88789 Jul 1 '19 at 13:23
  • $\begingroup$ @paw88789 Nope, there cannot be an edge from a vertex to itself. $\endgroup$ – CubbyKushi Jul 1 '19 at 14:01
4
$\begingroup$

For the given sequence, if we are talking about simple graphs, no such graph exists. You can conclude that by pure logical arguments:

  • We have $6$ vertices.
  • Two of them have degree $5$.
  • Then each of them are adjacent to every other vertices.
  • Then we cannot have a vertex with degree $1$ since we already know that every vertex is adjacent to at least two vertices, namely the ones with degree $5$.
  • Therefore no such graph exists.
| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

The answer by ArsenBerk is correct (assuming simple graphs), but since you are also asking how to get to that answer, here is how I found it:

It's never a bad idea to just try things if you're stuck. So we try to draw the graph. Well, there are six vertices, so we start by drawing them. Cool. Next, two of them have degree $5$, which is easy; no real choice involved here, so we just pick two vertices to be our degree-five vertices and draw the nine lines. From here, you can- Wait a second! Now each vertex has at least two edges already, but we wanted one vertex to have degree $1$. That's impossible.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

This is a well researched math problem (with answers!). The Erdos-Gallai theorem gives and if and and only if condition on whether a degree sequence can be realized and the Havel-Hakimi algorithm gives you a way to do it.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 for giving the general argument. I knew there was an inequality but I forgot its name so couldn't refer to it :/ $\endgroup$ – ArsenBerk Jul 1 '19 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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