The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem. That is, it answers the following question: Given a finite list of nonnegative integers in non-increasing order, is there a simple graph such that its degree sequence is exactly this list? A simple graph contains no double edges or loops.^[1] The degree sequence is a list of numbers in nonincreasing order indicating the number of edges incident to each vertex in the graph.^[2] If a simple graph exists for exactly the given degree sequence, the list of integers is called graphic. The Havel-Hakimi algorithm constructs a special solution if a simple graph for the given degree sequence 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).

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (June 2020)

The Havel-Hakimi algorithm is based on the following theorem.

Let ${\displaystyle A=(s,t_{1},...,t_{s},d_{1},...,d_{n})}$ be a finite list of nonnegative integers that is nonincreasing. Let ${\displaystyle A'=(t_{1}-1,...,t_{s}-1,d_{1},...,d_{n})}$ be a second finite list of nonnegative integers that is rearranged to be nonincreasing. List ${\displaystyle A}$ is graphic if and only if list ${\displaystyle A'}$ is graphic.

If the given list ${\displaystyle A}$ is graphic, then the theorem will be applied at most ${\displaystyle n-1}$ times setting in each further step ${\displaystyle A:=A'}$. Note that it can be necessary to sort this list again. This process ends when the whole list ${\displaystyle A'}$ consists of zeros. Let ${\displaystyle G}$ be a simple graph with the degree sequence ${\displaystyle A}$: Let the vertex ${\displaystyle S}$ have degree ${\displaystyle s}$; let the vertices ${\displaystyle T_{1},...,T_{s}}$ have respective degrees ${\displaystyle t_{1},...,t_{s}}$; let the vertices ${\displaystyle D_{1},...,D_{n}}$ have respective degrees ${\displaystyle d_{1},...,d_{n}}$. In each step of the algorithm, one constructs the edges of a graph with vertices ${\displaystyle T_{1},...,T_{s}}$—i.e., if it is possible to reduce the list ${\displaystyle A}$ to ${\displaystyle A'}$, then we add edges ${\displaystyle \{S,T_{1}\},\{S,T_{2}\},\cdots ,\{S,T_{s}\}}$. When the list ${\displaystyle A}$ cannot be reduced to a list ${\displaystyle A'}$ of nonnegative integers in any step of this approach, the theorem proves that the list ${\displaystyle A}$ from the beginning is not graphic.

Let ${\displaystyle 6,3,3,3,3,2,2,2,2,1,1}$ be a nonincreasing, finite degree sequence of nonnegative integers. To test whether this degree sequence is graphic, we apply the Havel-Hakimi algorithm:

First, we remove the vertex with the highest degree — in this case, ${\displaystyle 6}$ —  and all its incident edges to get ${\displaystyle 2,2,2,2,1,1,2,2,1,1}$ (assuming the vertex with highest degree is adjacent to the ${\displaystyle 6}$ vertices with next highest degree). We rearrange this sequence in nonincreasing order to get ${\displaystyle 2,2,2,2,2,2,1,1,1,1}$. We repeat the process, removing the vertex with the next highest degree to get ${\displaystyle 1,1,2,2,2,1,1,1,1}$ and rearranging to get ${\displaystyle 2,2,2,1,1,1,1,1,1}$. We continue this removal to get ${\displaystyle 1,1,1,1,1,1,1,1}$, and then ${\displaystyle 0,0,0,0,0,0,0,0}$. This sequence is clearly graphic, as it is the simple graph of ${\displaystyle 8}$ isolated vertices.

To show an example of a non-graphic sequence, let ${\displaystyle 6,5,5,4,3,2,1}$ be a nonincreasing, finite degree sequence of nonnegative integers. Applying the algorithm, we first remove the degree ${\displaystyle 6}$ vertex and all its incident edges to get ${\displaystyle 4,4,3,2,1,0}$. Already, we know this degree sequence is not graphic, since it claims to have ${\displaystyle 6}$ vertices with one vertex not adjacent to any of the other vertices; thus, the maximum degree of the other vertices is ${\displaystyle 4}$. This means that two of the vertices are connected to all the other vertices with the exception of the isolated one, so the minimum degree of each vertex should be ${\displaystyle 2}$; however, the sequence claims to have a vertex with degree ${\displaystyle 1}$. Thus, the sequence is not graphic.

For the sake of the algorithm, if we were to reiterate the process, we would get ${\displaystyle 3,2,1,0,0}$ which is yet more clearly not graphic. One vertex claims to have a degree of ${\displaystyle 3}$, and yet only two other vertices have neighbors. Thus the sequence cannot be graphic.

• Erdős–Gallai theorem