Havel–Hakimi algorithm

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

The algorithm

The Havel-Hakimi 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$ is 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.

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

Notes

^ From Shahriari (2022, p. 48): "Definition 2.17 (Graphs & Subgraphs). A simple graph (or just a graph) G is a pair of sets (V, E) where V is a nonempty set called the set of vertices of G, and E is a (possibly empty) set of unordered pairs of distinct elements of V. The set E is called the set of edges of G. If the number of vertices of G is finite, then G is a finite graph (or a finite simple graph)."
^ From Shahriari (2022, p. 355): "Definition 10.6 (The degree sequence of a graph; Graphic sequences). The degree sequence of a graph is the list of the degrees of its vertices in non-increasing order. A non-increasing sequence of non-negative integers is called graphic, if there exists a simple graph whose degree sequence is precisely that sequence.”

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.
Shahriari, Shahriar (2022), Invitation to Combinatorics, Cambridge U. Press.
West, Douglas B. (2001). Introduction to graph theory. Second Edition. Prentice Hall, 2001. 45-46.

[1] From Shahriari (2022, p. 48): "Definition 2.17 (Graphs & Subgraphs). A simple graph (or just a graph) G is a pair of sets (V, E) where V is a nonempty set called the set of vertices of G, and E is a (possibly empty) set of unordered pairs of distinct elements of V. The set E is called the set of edges of G. If the number of vertices of G is finite, then G is a finite graph (or a finite simple graph)."

[2] From Shahriari (2022, p. 355): "Definition 10.6 (The degree sequence of a graph; Graphic sequences). The degree sequence of a graph is the list of the degrees of its vertices in non-increasing order. A non-increasing sequence of non-negative integers is called graphic, if there exists a simple graph whose degree sequence is precisely that sequence.”

[1]

[2]

The algorithm

See also

Notes

References