Graph Theory – Constructing a Graph from a Degree Sequence

graph theorymatrices

Let's say I'm given several degree sequences like

$$\begin{array}{l}
\{4,3,3,2,2\} \\
\{3,3,3,3\} \\
\{5,3,3,2,2,1\}
\end{array}$$
I can find the number of edges using the handshaking lemma
$$
\sum_{v \in V} \operatorname{deg}(v)=2|E|
$$

But how do I construct a graph just given these degree sequences? There are multiple types of graphs that satisfy the degree sequences, but beyond guess & checking, is there a logic/pattern to follow when making graphs? Right now I'm at the guess & check stage.

Best Answer

If you have some requirements like planarity or connectedness, then you are left with trial and error. However, if you would like any simple graph with the given degree sequence, then you can do a simple algorithm:

  • Sort the degrees descending.
  • Connect the highest degree $d$ to the next $d$ vertices, e.g. $$(4,3,2,1,1,1) \leadsto (3-1,2-1,1-1,1-1,1) = (2,1,1).$$
  • Iterate until finished.

The idea behind it is rather simple, if you want the full proof, then you can find it here (Václav Havel, 1955, non-English). Some info is also available at MathWorld.

I hope this helps $\ddot\smile$

Related Question