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.
The algorithm was published by Havel (1955), and later by Hakimi (1962).
The Havel-Hakimi algorithm is based on the following theorem.
be a finite list of nonnegative integers that is nonincreasing.
be a second finite list of nonnegative integers that is rearranged to be nonincreasing.
be a simple graph with the degree sequence
In each step of the algorithm, one constructs the edges of a graph with vertices
of nonnegative integers in any step of this approach, the theorem proves that the list
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
is graphic, and there exists a simple graph
is graphic, and there exists a simple graph
with all its incident edges to obtain the degree sequence
This modification preserves the degree sequence of
while maintaining the original degree sequence
using the above method, and then we have the first case once more, through which we can obtain the degree sequence
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,
(assuming the vertex with highest degree is adjacent to the
We rearrange this sequence in nonincreasing order to get
We repeat the process, removing the vertex with the next highest degree to get
This sequence is clearly graphic, as it is the simple graph of
be a nonincreasing, finite degree sequence of nonnegative integers.
Applying the algorithm, we first remove the degree
Already, we know this degree sequence is not graphic, since it claims to have
; however, the sequence claims to have a vertex with degree