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.