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 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.

...
Wikipedia