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.^[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 Havel–Hakimi algorithm is based on the following theorem.

Let ${\displaystyle A=(s,t_{1},...,t_{s},d_{1},...,d_{n})}${\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})}${\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}${\displaystyle A} is graphic if and only if list ${\displaystyle A'}${\displaystyle A'} is graphic.

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

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'}${\displaystyle A'} is graphic, and there exists a simple graph ${\displaystyle G'}${\displaystyle G'} with the degree sequence ${\displaystyle A'=(t_{1}-1,...,t_{s}-1,d_{1},...,d_{n})}${\displaystyle A'=(t_{1}-1,...,t_{s}-1,d_{1},...,d_{n})}. Then we add a new vertex ${\displaystyle v}${\displaystyle v} adjacent to the ${\displaystyle s}${\displaystyle s} vertices with degrees ${\displaystyle t_{1}-1,...,t_{s}-1}${\displaystyle t_{1}-1,...,t_{s}-1} to obtain the degree sequence ${\displaystyle A}${\displaystyle A}.

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

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

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

Since ${\displaystyle t_{i}\geq d_{j}}${\displaystyle t_{i}\geq d_{j}}, we have two possibilities: Either ${\displaystyle t_{i}=d_{j}}${\displaystyle t_{i}=d_{j}}, or ${\displaystyle t_{i}>d_{j}}${\displaystyle t_{i}>d_{j}}. If ${\displaystyle t_{i}=d_{j}}${\displaystyle t_{i}=d_{j}}, then by switching the places of the vertices ${\displaystyle T_{i}}${\displaystyle T_{i}} and ${\displaystyle D_{j}}${\displaystyle D_{j}}, we can adjust ${\displaystyle G}${\displaystyle G} so that ${\displaystyle S}${\displaystyle S} is adjacent to ${\displaystyle T_{i}}${\displaystyle T_{i}} instead of ${\displaystyle D_{j}.}${\displaystyle D_{j}.} If ${\displaystyle t_{i}>d_{j}}${\displaystyle t_{i}>d_{j}}, then since ${\displaystyle T_{i}}${\displaystyle T_{i}} is adjacent to more vertices than ${\displaystyle D_{j}}${\displaystyle D_{j}}, let another vertex ${\displaystyle W}${\displaystyle W} be adjacent to ${\displaystyle T_{i}}${\displaystyle T_{i}} and not ${\displaystyle D_{j}}${\displaystyle D_{j}}. Then we can adjust ${\displaystyle G}${\displaystyle G} by removing the edges ${\displaystyle \left\{S,D_{j}\right\}}${\displaystyle \left\{S,D_{j}\right\}} and ${\displaystyle \left\{T_{i},W\right\}}${\displaystyle \left\{T_{i},W\right\}}, and adding the edges ${\displaystyle \left\{S,T_{i}\right\}}${\displaystyle \left\{S,T_{i}\right\}} and ${\displaystyle \left\{W,D_{j}\right\}}${\displaystyle \left\{W,D_{j}\right\}}. This modification preserves the degree sequence of ${\displaystyle G}${\displaystyle G}, but the vertex ${\displaystyle S}${\displaystyle S} is now adjacent to ${\displaystyle T_{i}}${\displaystyle T_{i}} instead of ${\displaystyle D_{j}}${\displaystyle D_{j}}. In this way, any vertex not connected to ${\displaystyle S}${\displaystyle S} can be adjusted accordingly so that ${\displaystyle S}${\displaystyle S} is adjacent to ${\displaystyle T_{i}}${\displaystyle T_{i}} while maintaining the original degree sequence ${\displaystyle A}${\displaystyle A} of ${\displaystyle G}${\displaystyle G}. Thus any vertex not connected to ${\displaystyle S}${\displaystyle S} can be connected to ${\displaystyle S}${\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'}${\displaystyle A'}. Hence, ${\displaystyle A}${\displaystyle A} is graphic if and only if ${\displaystyle A'}${\displaystyle A'} is also graphic.

Let ${\displaystyle 6,3,3,3,3,2,2,2,2,1,1}${\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}${\displaystyle 6} —  and all its incident edges to get ${\displaystyle 2,2,2,2,1,1,2,2,1,1}${\displaystyle 2,2,2,2,1,1,2,2,1,1} (assuming the vertex with highest degree is adjacent to the ${\displaystyle 6}${\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}${\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}${\displaystyle 1,1,2,2,2,1,1,1,1} and rearranging to get ${\displaystyle 2,2,2,1,1,1,1,1,1}${\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}${\displaystyle 1,1,1,1,1,1,1,1}, and then ${\displaystyle 0,0,0,0,0,0,0,0}${\displaystyle 0,0,0,0,0,0,0,0}. This sequence is clearly graphic, as it is the simple graph of ${\displaystyle 8}${\displaystyle 8} isolated vertices.

To show an example of a non-graphic sequence, let ${\displaystyle 6,5,5,4,3,2,1}${\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}${\displaystyle 6} vertex and all its incident edges to get ${\displaystyle 4,4,3,2,1,0}${\displaystyle 4,4,3,2,1,0}. Already, we know this degree sequence is not graphic, since it claims to have ${\displaystyle 6}${\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}${\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}${\displaystyle 2}; however, the sequence claims to have a vertex with degree ${\displaystyle 1}${\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}${\displaystyle 3,2,1,0,0} which is yet more clearly not graphic. One vertex claims to have a degree of ${\displaystyle 3}${\displaystyle 3}, and yet only two other vertices have neighbors. Thus the sequence cannot be graphic.

• Erdős–Gallai theorem

• Havel, Václav (1955), "A remark on the existence of finite graphs", Časopis pro pěstování matematiky (in Czech), 80 (4): 477–480, doi:10.21136/CPM.1955.108220
• 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 (3): 496–506, doi:10.1137/0110037, 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.

• Graph algorithms

• Articles with short description
• Short description matches Wikidata
• Articles lacking in-text citations from June 2020
• All articles lacking in-text citations
• CS1 Czech-language sources (cs)