Havel–Hakimi algorithm

The algorithm is based on the following theorem.

Let ${\displaystyle S=(d_{1},\dots ,d_{n})}$ be a finite list of nonnegative integers that is nonincreasing. List ${\displaystyle S}$ is graphic if and only if the finite list ${\displaystyle 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 ${\displaystyle S}$ is graphic then the theorem will be applied at most ${\displaystyle n-1}$ times setting in each further step ${\displaystyle S:=S'}$. Note that it can be necessary to sort this list again. This process ends when the whole list ${\displaystyle S'}$ consists of zeros. In each step of the algorithm one constructs the edges of a graph with vertices ${\displaystyle v_{1},\cdots ,v_{n}}$, i.e. if it is possible to reduce the list ${\displaystyle S}$ to ${\displaystyle S'}$, then we add edges ${\displaystyle \{v_{1},v_{2}\},\{v_{1},v_{3}\},\cdots ,\{v_{1},v_{d_{1}+1}\}}$. When the list ${\displaystyle S}$ cannot be reduced to a list ${\displaystyle S'}$ of nonnegative integers in any step of this approach, the theorem proves that the list ${\displaystyle S}$ from the beginning is not graphic.

The time complexity of the algorithm is ${\displaystyle O(n^{2})}$.

• Erdős–Gallai theorem

• 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.
• West, Douglas B. (2001). Introduction to graph theory. Second Edition. Prentice Hall, 2001. 45-46.