Degree sequences & the graph realisation problem

Introduction

Given a graph \(G=(V,E)\) comprising a set of vertices \(V\) and edges \(E\), the degree \(d(v)\) of a vertex \(v\in V\) is the number of edges incident to \(v\); that is, the number of neighbours of \(v\). The degree sequence of \(G\) is then the sequence \[\left(d(v_1),d(v_2),\ldots,d(v_n)\right) \qquad d(v_1)\geq d(v_2) \geq\ldots \geq d(v_n)\]

Try it yourself. Use the below widget to create a graph and check you agree with the degree sequence shown.

Graph Realisation

On the other hand, one may ask whether, for a finite sequence of non-negative integers \(\left(d_1,d_2,\ldots,d_n\right)\), there exists a graph with degree sequence \(\left(d_1,d_2,\ldots,d_n\right)\). This is the graph realisation problem.

It should be apparent that existence is not guaranteed. For example, \(\left(0,1\right)\) clearly cannot be the degree sequence of any (simple) graph. We say that \(\left(0,1\right)\) is non-graphic.

Beyond consisting of non-negative integers only, a most basic necessary condition for a degree sequence to be graphic comes from the handshaking lemma, which states that the sum of all degrees equals twice the number of edges: \[\sum_{v\in V}d(v) = 2 \lvert E \rvert\] Consequently, \(\sum_{v\in V}d(v)\) must be even. This allows us to immediately discount the sequence \(\left(3,2,1,1\right)\), for example, but not \(\left(3,1,1,1\right)\). In fact, the latter is graphic:

How might we verify this without actually constructing the graph?

The Erdős-Gallai Theorem

The Erdős-Gallai theorem provides a solution to the graph realisation problem. It may be stated as follows:

A non-increasing sequence of non-negative integers \(\left(d_1,d_2,\ldots,d_n\right)\) is the representation of a graph on \(n\) vertices if and only if \(\sum_{i=1}^n d_i\) is even and \[\sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^n \min\left\{d_i,k\right\}\] for each \(k \in \{1,\ldots,n\}\).

Take the sequence \((3,1,1,1)\). As \(d_1=3\) and \(d_2=d_3=d_4=1\), at each \(k \in\{1,2,3,4\}\) we have \(\min\left\{d_i,k\right\} = 1\) whilst \[ \sum_{i=1}^4d_i = 6 \] is even. Then \[ \begin{align} k=1:\qquad& d_1=3\leq 1(0) + \sum_{i=2}^41 = 3 \\ k=2:\qquad& d_1+d_2=4\leq 2(1) + \sum_{i=3}^41 = 4 \\ k=3:\qquad& d_1+d_2+d_3=5\leq 3(2) + \sum_{i=4}^4 1 = 7\\[8pt] k=4:\qquad& d_1+d_2+d_3+d_4=6\leq 4(3) = 12, \end{align} \] confirming that this sequence is graphic.

Try it yourself. Come up with several sequences and determine whether they are graphic using the Erdős-Gallai theorem. Use the below tool to check your answers.

Degree Sequence:

Graphic

Non-Graphic

The Havel-Hakimi Algorithm

While the Erdős-Gallai theorem provides an efficient test as to whether a sequence is graphic, it does not provide a means of constructing a graph with that degree sequence in the case of a positive result. In contrast, the Havel-Hakimi algorithm provides a constructive solution to the graph realisation problem. It is a recursive algorithm based on the following theorem:

A non-increasing sequence \(S=\left(d_1,d_2,\ldots,d_n\right)\) of non-negative integers is graphic if and only if the sequence \[S'=\bigl(\underbrace{d_2-1,d_3-1,\ldots,d_{d_1+1}-1}_{d_1 \ \text{terms}},d_{d_1+2},\ldots,d_n\bigr)\] comprises non-negative integers and (when sorted) is graphic.

Equipped with this theorem, the procedure to check whether a given sequence \(S_0=\left(d_1,d_2,\ldots,d_n\right)\) is graphic is straightforward:

1. Remove the first element \(d_1\) of \(S_0\) and subtract 1 from the next \(d_1\) elements, sorting the remaining elements to form a non-increasing sequence \(S_1\). If this is not possible (there are fewer than \(d_1\) terms in the truncated sequence) or \(S_1\) contains a negative integer, \(S_1\), and therefore \(S_0\), is non-graphic.
2. Repeat to generate \(S_2,S_3,\ldots\). If at any stage there are too few terms to subtract 1 from, or a non-negative integer is encountered, the original sequence is non-graphic. Otherwise, after at most \(n-1\) steps, a sequence \(S_F\) of zeros will result. As \(S_F\) clearly has a graphical representation (a collection of 1 or more unconnected vertices), so does \(S_0\).

Graphically, in the \(i^{\text{th}}\) iteration we attach the vertex with the greatest degree \(d(v_{\text{max}})\) to the \(d(v_{\text{max}})\) vertices of next greatest degree, repeating until we either cannot 'exhaust' a particular vertex (i.e. it has a degree larger than the sum of degrees of the remaining vertices) and the algorithm fails to produce a graph, or we reach a situation where none of remaining vertices require further neighbours (\(S_F=(0,\ldots,0)\)), and a graph has been completed.

In fact, in each iteration one is free to chose any one of the \(d_i\) to be removed, provided it is still the greatest \(d_i\) terms that are decremented, with different choices at each step producing a variety of graphical representations.

As a demonstration, consider the sequence \(S_0=\left(3,2,2,1,1,1\right)\). The labels \(v_0,\ldots,v_5\) will be used to keep track of the vertices as in \[S_0 =(\overset{v_0}{3},\overset{v_1}{2},\overset{v_2}{2},\overset{v_3}{1},\overset{v_4}{1},\overset{v_5}{1})\]

1. Attach \(v_0\) to \(v_1\), \(v_2\) and \(v_3\). Remember to sort the truncated sequence: \[S_1=(\overset{v_1}{1},\overset{v_2}{1},\overset{v_3}{0},\overset{v_4}{1},\overset{v_5}{1} )\to (\overset{v_1}{1},\overset{v_2}{1},\overset{v_4}{1},\overset{v_5}{1},\overset{v_3}{0})\]
2. Attach \(v_1\) to \(v_2\): \[S_2=(\overset{v_2}{0},\overset{v_4}{1},\overset{v_5}{1},\overset{v_3}{0}) \to(\overset{v_4}{1},\overset{v_5}{1},\overset{v_2}{0}, \overset{v_3}{0})\]
3. Finally, join \(v_4\) and \(v_5\): \[S_3=(\overset{v_5}{0},\overset{v_2}{0},\overset{v_3}{0})=S_F\]

The below widget illustrates each step:

Observe that the graph produced is not connected (no path exists between \(v_4\) and \(v_0\), for example). As mentioned above, it is not necessary to select the greatest term for removal with each iteration. It turns out that if instead the least term is chosen each time, the resulting graph will always be connected if a connected realisation exists.

Try if for yourself. The below widget performs the Havel-Hakimi algorithm to produce a connected graph from any degree sequence. Come up with a valid degree sequence and see if you can match its output.

Degree Sequence: Generate