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. 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 $A=(s,t_{1},...,t_{s},d_{1},...,d_{n})$ be a finite list of nonnegative integers that is nonincreasing. Let $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 $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_{1},...,T_{s}$ have respective degrees $t_{1},...,t_{s}$; let the vertices $D_{1},...,D_{n}$ have respective degrees $d_{1},...,d_{n}$. In each step of the algorithm, one constructs the edges of a graph with vertices $T_{1},...,T_{s}$—i.e., if it is possible to reduce the list $A$ to $A'$, then we add edges $\{S,T_{1}\},\{S,T_{2}\},\cdots ,\{S,T_{s}\}$. 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}-1,...,t_{s}-1,d_{1},...,d_{n})$. Then we add a new vertex $v$ adjacent to the $s$ vertices with degrees $t_{1}-1,...,t_{s}-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_{1},...,t_{s},d_{1},...,d_{n})$ and vertices $S,T_{1},...,T_{s},D_{1},...,D_{n}$. 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_{1},...,T_{s}$ 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_{i}$ for some $1\leq i\leq s$ in $G$. Then we can change the graph $G$ so that $S$ is adjacent to $T_{i}$ while maintaining the same degree sequence $A$. Since $S$ has degree $s$, the vertex $S$ must be adjacent to some vertex $D_{j}$ in $G$ for $1\leq j\leq n$: Let the degree of $D_{j}$ be $d_{j}$. 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_{i}$ and $D_{j}$, we can adjust $G$ so that $S$ is adjacent to $T_{i}$ instead of $D_{j}.$ If $t_{i}>d_{j}$, then since $T_{i}$ is adjacent to more vertices than $D_{j}$, let another vertex $W$ be adjacent to $T_{i}$ and not $D_{j}$. Then we can adjust $G$ by removing the edges $\left\{S,D_{j}\right\}$ and $\left\{T_{i},W\right\}$, and adding the edges $\left\{S,T_{i}\right\}$ and $\left\{W,D_{j}\right\}$. This modification preserves the degree sequence of $G$, but the vertex $S$ is now adjacent to $T_{i}$ instead of $D_{j}$. In this way, any vertex not connected to $S$ can be adjusted accordingly so that $S$ is adjacent to $T_{i}$ 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

References

• Havel, Václav (1955), "A remark on the existence of finite graphs", Časopis pro pěstování matematiky (in Czech), 80: 477–480
• Hakimi, S. L. (1962), "On realizability of a set of integers as degrees of the vertices of a linear graph. I", Journal of the Society for Industrial and Applied Mathematics, 10: 496–506, MR 0148049.
• Shahriari, Shahriar (2022), Invitation to Combinatorics, Cambridge U. Press.
• West, Douglas B. (2001). Introduction to graph theory. Second Edition. Prentice Hall, 2001. 45-46.