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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.