Havel–Hakimi algorithm

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

The algorithm is based on the following theorem.

Let $S=(d_1,\dots,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,\dots,d_{d_1+1}-1,d_{d_1+2},\dots,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,\cdots,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\},\cdots,\{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.

See also

• Erdős–Gallai theorem

References

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