The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem, i.e. the question if there exists for a finite list of nonnegative integers a simple graph such that its degree sequence is exactly this list. For a positive answer the list of integers is called graphic. The algorithm constructs a special solution if one 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 is based on the following theorem.
Let S = ( d 1 , … , d n ) be a finite list of nonnegative integers that is nonincreasing. List S is graphic if and only if the finite list S ′ = ( d 2 − 1 , d 3 − 1 , … , d d 1 + 1 − 1 , d d 1 + 2 , … , d n ) has nonnegative integers and is graphic.
If the given list S graphic then the theorem will be applied at most n − 1 times setting in each further step S := S ′ . Note that it can be necessary to sort this list again. This process ends when the whole list S ′ consists of zeros. In each step of the algorithm one constructs the edges of a graph with vertices v 1 , ⋯ , v n , i.e. if it is possible to reduce the list S to S ′ , then we add edges { v 1 , v 2 } , { v 1 , v 3 } , ⋯ , { v 1 , v d 1 + 1 } . When the list S cannot be reduced to a list S ′ of nonnegative integers in any step of this approach, the theorem proves that the list S from the beginning is not graphic.
