Havel-Hakimi algorithm

The Havel-Hakimi algorithm is a graph theory algorithm that solves the graph realization problem, which asks whether, for a finite list of nonnegative integers in non-increasing order, there is a simple graph, with no double edges or loops, whose degree sequence is exactly that list. A list for which such a graph exists is called graphic. The algorithm either constructs one such graph or proves that none exists, and the construction is recursive. It relies on a theorem that a list is graphic exactly when the list obtained by removing its first number s and subtracting 1 from the next s numbers, then re-sorting, is also graphic. Applying this at most n-1 times either reduces the list to all zeros, in which case the graph has been built edge by edge, or fails at some step because a number would become negative or too few entries remain, which proves the original list is not graphic. The result was published by Havel in 1955 and later by Hakimi in 1962.