# Havel–Hakimi algorithm

Short description: Algorithm in graph theory

The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem. That is, it answers the following question: Given a finite list of nonnegative integers in non-increasing order, is there a simple graph such that its degree sequence is exactly this list? A simple graph contains no double edges or loops.[1] The degree sequence is a list of numbers in nonincreasing order indicating the number of edges incident to each vertex in the graph.[2] If a simple graph exists for exactly the given degree sequence, the list of integers is called graphic. The Havel-Hakimi algorithm constructs a special solution if a simple graph for the given degree sequence exists, or proves that one cannot find a positive answer. This construction is based on a recursive algorithm. The algorithm was published by (Havel 1955), and later by (Hakimi 1962).

## The algorithm

The Havel-Hakimi algorithm is based on the following theorem.

Let $\displaystyle{ A = (s, t_{1},..., t_{s}, d_{1},..., d_{n}) }$ be a finite list of nonnegative integers that is nonincreasing. Let $\displaystyle{ A' = (t_{1}-1,..., t_{s}-1, d_{1},..., d_{n}) }$ be a second finite list of nonnegative integers that is rearranged to be nonincreasing. List $\displaystyle{ A }$ is graphic if and only if list $\displaystyle{ A' }$ is graphic.

If the given list $\displaystyle{ A }$ is graphic, then the theorem will be applied at most $\displaystyle{ n-1 }$ times setting in each further step $\displaystyle{ A:=A' }$. Note that it can be necessary to sort this list again. This process ends when the whole list $\displaystyle{ A' }$ consists of zeros. Let $\displaystyle{ G }$ be a simple graph with the degree sequence $\displaystyle{ A }$: Let the vertex $\displaystyle{ S }$ have degree $\displaystyle{ s }$; let the vertices $\displaystyle{ T_{1},..., T_{s} }$ have respective degrees $\displaystyle{ t_{1},..., t_{s} }$; let the vertices $\displaystyle{ D_{1},..., D_{n} }$ have respective degrees $\displaystyle{ d_{1},..., d_{n} }$. In each step of the algorithm, one constructs the edges of a graph with vertices $\displaystyle{ T_{1},..., T_{s} }$—i.e., if it is possible to reduce the list $\displaystyle{ A }$ to $\displaystyle{ A' }$, then we add edges $\displaystyle{ \{S,T_1\},\{S,T_2\},\cdots,\{S,T_{s}\} }$. When the list $\displaystyle{ A }$ cannot be reduced to a list $\displaystyle{ A' }$ of nonnegative integers in any step of this approach, the theorem proves that the list $\displaystyle{ A }$ from the beginning is not graphic.

### Proof

The following is a summary based on the proof of the Havel-Hakimi algorithm in Invitation to Combinatorics (Shahriari 2022).

To prove the Havel-Hakimi algorithm always works, assume that $\displaystyle{ A' }$ is graphic, and there exists a simple graph $\displaystyle{ G' }$ with the degree sequence $\displaystyle{ A' = (t_{1}-1,..., t_{s}-1, d_{1},..., d_{n}) }$. Then we add a new vertex $\displaystyle{ v }$ adjacent to the $\displaystyle{ s }$ vertices with degrees $\displaystyle{ t_{1}-1,..., t_{s}-1 }$ to obtain the degree sequence $\displaystyle{ A }$.

To prove the other direction, assume that $\displaystyle{ A }$ is graphic, and there exists a simple graph $\displaystyle{ G }$ with the degree sequence $\displaystyle{ A = (s, t_{1},..., t_{s}, d_{1},..., d_{n}) }$ and vertices $\displaystyle{ S, T_{1},..., T_{s}, D_{1},..., D_{n} }$. We do not know which $\displaystyle{ s }$ vertices are adjacent to $\displaystyle{ S }$, so we have two possible cases.

In the first case, $\displaystyle{ S }$ is adjacent to the vertices $\displaystyle{ T_{1},..., T_{s} }$ in $\displaystyle{ G }$. In this case, we remove $\displaystyle{ S }$ with all its incident edges to obtain the degree sequence $\displaystyle{ A' }$.

In the second case, $\displaystyle{ S }$ is not adjacent to some vertex $\displaystyle{ T_{i} }$ for some $\displaystyle{ 1 \leq i \leq s }$ in $\displaystyle{ G }$. Then we can change the graph $\displaystyle{ G }$ so that $\displaystyle{ S }$ is adjacent to $\displaystyle{ T_{i} }$ while maintaining the same degree sequence $\displaystyle{ A }$. Since $\displaystyle{ S }$ has degree $\displaystyle{ s }$, the vertex $\displaystyle{ S }$ must be adjacent to some vertex $\displaystyle{ D_{j} }$ in $\displaystyle{ G }$ for $\displaystyle{ 1 \leq j \leq n }$: Let the degree of $\displaystyle{ D_{j} }$ be $\displaystyle{ d_{j} }$. We know $\displaystyle{ t_i \geq d_j }$, as the degree sequence $\displaystyle{ A }$ is in non-increasing order.

Since $\displaystyle{ t_i \geq d_j }$, we have two possibilities: Either $\displaystyle{ t_i = d_j }$, or $\displaystyle{ t_i \gt d_j }$. If $\displaystyle{ t_i = d_j }$, then by switching the places of the vertices $\displaystyle{ T_{i} }$ and $\displaystyle{ D_{j} }$, we can adjust $\displaystyle{ G }$ so that $\displaystyle{ S }$ is adjacent to $\displaystyle{ T_{i} }$ instead of $\displaystyle{ D_{j}. }$ If $\displaystyle{ t_i \gt d_j }$, then since $\displaystyle{ T_{i} }$ is adjacent to more vertices than $\displaystyle{ D_{j} }$, let another vertex $\displaystyle{ W }$ be adjacent to $\displaystyle{ T_{i} }$ and not $\displaystyle{ D_{j} }$. Then we can adjust $\displaystyle{ G }$ by removing the edges $\displaystyle{ \left \{ S, D_j \right \} }$ and $\displaystyle{ \left \{ T_i, W \right \} }$, and adding the edges $\displaystyle{ \left \{ S, T_i \right \} }$ and $\displaystyle{ \left \{ W, D_j\right \} }$. This modification preserves the degree sequence of $\displaystyle{ G }$, but the vertex $\displaystyle{ S }$ is now adjacent to $\displaystyle{ T_{i} }$ instead of $\displaystyle{ D_{j} }$. In this way, any vertex not connected to $\displaystyle{ S }$ can be adjusted accordingly so that $\displaystyle{ S }$ is adjacent to $\displaystyle{ T_{i} }$ while maintaining the original degree sequence $\displaystyle{ A }$ of $\displaystyle{ G }$. Thus any vertex not connected to $\displaystyle{ S }$ can be connected to $\displaystyle{ S }$ using the above method, and then we have the first case once more, through which we can obtain the degree sequence $\displaystyle{ A' }$. Hence, $\displaystyle{ A }$ is graphic if and only if $\displaystyle{ A' }$ is also graphic.

## Examples

Let $\displaystyle{ 6, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1 }$ be a nonincreasing, finite degree sequence of nonnegative integers. To test whether this degree sequence is graphic, we apply the Havel-Hakimi algorithm:

First, we remove the vertex with the highest degree — in this case, $\displaystyle{ 6 }$ —  and all its incident edges to get $\displaystyle{ 2, 2, 2, 2, 1, 1, 2, 2, 1, 1 }$ (assuming the vertex with highest degree is adjacent to the $\displaystyle{ 6 }$ vertices with next highest degree). We rearrange this sequence in nonincreasing order to get $\displaystyle{ 2, 2, 2, 2, 2, 2, 1, 1, 1, 1 }$. We repeat the process, removing the vertex with the next highest degree to get $\displaystyle{ 1, 1, 2, 2, 2, 1, 1, 1, 1 }$ and rearranging to get $\displaystyle{ 2, 2, 2, 1, 1, 1, 1, 1, 1 }$. We continue this removal to get $\displaystyle{ 1, 1, 1, 1, 1, 1, 1, 1 }$, and then $\displaystyle{ 0, 0, 0, 0, 0, 0, 0, 0 }$. This sequence is clearly graphic, as it is the simple graph of $\displaystyle{ 8 }$ isolated vertices.

To show an example of a non-graphic sequence, let $\displaystyle{ 6, 5, 5, 4, 3, 2, 1 }$ be a nonincreasing, finite degree sequence of nonnegative integers. Applying the algorithm, we first remove the degree $\displaystyle{ 6 }$ vertex and all its incident edges to get $\displaystyle{ 4, 4, 3, 2, 1, 0 }$. Already, we know this degree sequence is not graphic, since it claims to have $\displaystyle{ 6 }$ vertices with one vertex not adjacent to any of the other vertices; thus, the maximum degree of the other vertices is $\displaystyle{ 4 }$. This means that two of the vertices are connected to all the other vertices with the exception of the isolated one, so the minimum degree of each vertex should be $\displaystyle{ 2 }$; however, the sequence claims to have a vertex with degree $\displaystyle{ 1 }$. Thus, the sequence is not graphic.

For the sake of the algorithm, if we were to reiterate the process, we would get $\displaystyle{ 3, 2, 1, 0, 0 }$ which is yet more clearly not graphic. One vertex claims to have a degree of $\displaystyle{ 3 }$, and yet only two other vertices have neighbors. Thus the sequence cannot be graphic.