Havel–Hakimi Algorithm

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. The degree sequence is a list of numbers in nonincreasing order indicating the number of edges incident to each vertex in the graph.From Shahriari (2022, p. 355): "Definition 10.6 (The degree sequence of a graph; Graphic sequences). The ''degree sequence'' of a graph is the list of the degrees of its vertices in non-increasing order. A non-increasing sequence of non-negative integers is called ''graphic'', if there exists a simple graph whose degree sequence is precisely that sequence.” 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 , and later by .

The algorithm

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

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

If the given list $A$ is graphic, then the theorem will be applied at most $n-1$ times setting in each further step $A:=A'$. Note that it can be necessary to sort this list again. This process ends when the whole list $A'$ consists of zeros. Let $G$ be a simple graph with the degree sequence $A$: Let the vertex $S$ have degree $s$; let the vertices $T_,..., T_$ have respective degrees $t_,..., t_$; let the vertices $D_,..., D_$ have respective degrees $d_,..., d_$. In each step of the algorithm, one constructs the edges of a graph with vertices $T_,..., T_$—i.e., if it is possible to reduce the list $A$ to $A'$, then we add edges $\,\,\cdots,\$. When the list $A$ cannot be reduced to a list $A'$ of nonnegative integers in any step of this approach, the theorem proves that the list $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 $A'$ is graphic, and there exists a simple graph $G'$ with the degree sequence $A' = (t_-1,..., t_-1, d_,..., d_)$. Then we add a new vertex $v$ adjacent to the $s$ vertices with degrees $t_-1,..., t_-1$ to obtain the degree sequence $A$.

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

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

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

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

Examples

Let $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, $6$ —  and all its incident edges to get $2, 2, 2, 2, 1, 1, 2, 2, 1, 1$ (assuming the vertex with highest degree is adjacent to the $6$ vertices with next highest degree). We rearrange this sequence in nonincreasing order to get $2, 2, 2, 2, 2, 2, 1, 1, 1, 1$. We repeat the process, removing the vertex with the next highest degree to get $1, 1, 2, 2, 2, 1, 1, 1, 1$ and rearranging to get $2, 2, 2, 1, 1, 1, 1, 1, 1$. We continue this removal to get $1, 1, 1, 1, 1, 1, 1, 1$, and then $0, 0, 0, 0, 0, 0, 0, 0$. This sequence is clearly graphic, as it is the simple graph of $8$ isolated vertices.

To show an example of a non-graphic sequence, let $6, 5, 5, 4, 3, 2, 1$ be a nonincreasing, finite degree sequence of nonnegative integers. Applying the algorithm, we first remove the degree $6$ vertex and all its incident edges to get $4, 4, 3, 2, 1, 0$. Already, we know this degree sequence is not graphic, since it claims to have $6$ vertices with one vertex not adjacent to any of the other vertices; thus, the maximum degree of the other vertices is $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 $2$; however, the sequence claims to have a vertex with degree $1$. Thus, the sequence is not graphic.

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

See also

*Erdős–Gallai theorem

Notes

References

*
*.
*
* West, Douglas B. (2001). ''Introduction to graph theory. Second Edition.'' Prentice Hall, 2001. 45-46.
{{DEFAULTSORT:Havel-Hakimi algorithm

Graph algorithms