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).

Algorithm

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

Let 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 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 A {\displaystyle A} is graphic if and only if list A ′ {\displaystyle A'} is graphic.

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

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

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

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

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

Examples

Let 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, 6 {\displaystyle 6} — and all its incident edges to get 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 6 {\displaystyle 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 {\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 1 , 1 , 2 , 2 , 2 , 1 , 1 , 1 , 1 {\displaystyle 1,1,2,2,2,1,1,1,1} and rearranging to get 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 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 {\displaystyle 1,1,1,1,1,1,1,1}, and then 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 8 {\displaystyle 8} isolated vertices.

To show an example of a non-graphic sequence, let 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 6 {\displaystyle 6} vertex and all its incident edges to get 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 6 {\displaystyle 6} vertices with one vertex not adjacent to any of the other vertices; thus, the maximum degree of the other vertices is 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 2 {\displaystyle 2}; however, the sequence claims to have a vertex with degree 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 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 3 {\displaystyle 3}, and yet only two other vertices have neighbors. Thus the sequence cannot be graphic.

See also

Notes