Misplaced Pages

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (June 2020) (Learn how and when to remove this message)

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. The degree sequence is a list of numbers in nonincreasing order indicating the number of edges incident to each vertex in the graph. 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 ${\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.

Proof

The following is a summary based on the proof of the Havel-Hakimi algorithm in Invitation to Combinatorics (Shahriari 2022).

To prove the Havel-Hakimi algorithm always works, assume that ${\displaystyle A'}$ is graphic, and there exists a simple graph ${\displaystyle G'}$ with the degree sequence ${\displaystyle A'=(t_{1}-1,...,t_{s}-1,d_{1},...,d_{n})}$. Then we add a new vertex ${\displaystyle v}$ adjacent to the ${\displaystyle s}$ vertices with degrees ${\displaystyle t_{1}-1,...,t_{s}-1}$ to obtain the degree sequence ${\displaystyle A}$.

To prove the other direction, assume that ${\displaystyle A}$ is graphic, and there exists a simple graph ${\displaystyle G}$ with the degree sequence ${\displaystyle A=(s,t_{1},...,t_{s},d_{1},...,d_{n})}$ and vertices ${\displaystyle S,T_{1},...,T_{s},D_{1},...,D_{n}}$. We do not know which ${\displaystyle s}$ vertices are adjacent to ${\displaystyle S}$, so we have two possible cases.

In the first case, ${\displaystyle S}$ is adjacent to the vertices ${\displaystyle T_{1},...,T_{s}}$ in ${\displaystyle G}$. In this case, we remove ${\displaystyle S}$ with all its incident edges to obtain the degree sequence ${\displaystyle A'}$.

In the second case, ${\displaystyle S}$ is not adjacent to some vertex ${\displaystyle T_{i}}$ for some ${\displaystyle 1\leq i\leq s}$ in ${\displaystyle G}$. Then we can change the graph ${\displaystyle G}$ so that ${\displaystyle S}$ is adjacent to ${\displaystyle T_{i}}$ while maintaining the same degree sequence ${\displaystyle A}$. Since ${\displaystyle S}$ has degree ${\displaystyle s}$, the vertex ${\displaystyle S}$ must be adjacent to some vertex ${\displaystyle D_{j}}$ in ${\displaystyle G}$ for ${\displaystyle 1\leq j\leq n}$: Let the degree of ${\displaystyle D_{j}}$ be ${\displaystyle d_{j}}$. We know ${\displaystyle t_{i}\geq d_{j}}$, as the degree sequence ${\displaystyle A}$ is in non-increasing order.

Since ${\displaystyle t_{i}\geq d_{j}}$, we have two possibilities: Either ${\displaystyle t_{i}=d_{j}}$, or ${\displaystyle t_{i}>d_{j}}$. If ${\displaystyle t_{i}=d_{j}}$, then by switching the places of the vertices ${\displaystyle T_{i}}$ and ${\displaystyle D_{j}}$, we can adjust ${\displaystyle G}$ so that ${\displaystyle S}$ is adjacent to ${\displaystyle T_{i}}$ instead of ${\displaystyle D_{j}.}$ If ${\displaystyle t_{i}>d_{j}}$, then since ${\displaystyle T_{i}}$ is adjacent to more vertices than ${\displaystyle D_{j}}$, let another vertex ${\displaystyle W}$ be adjacent to ${\displaystyle T_{i}}$ and not ${\displaystyle D_{j}}$. Then we can adjust ${\displaystyle G}$ by removing the edges ${\displaystyle \left\{S,D_{j}\right\}}$ and ${\displaystyle \left\{T_{i},W\right\}}$, and adding the edges ${\displaystyle \left\{S,T_{i}\right\}}$ and ${\displaystyle \left\{W,D_{j}\right\}}$. This modification preserves the degree sequence of ${\displaystyle G}$, but the vertex ${\displaystyle S}$ is now adjacent to ${\displaystyle T_{i}}$ instead of ${\displaystyle D_{j}}$. In this way, any vertex not connected to ${\displaystyle S}$ can be adjusted accordingly so that ${\displaystyle S}$ is adjacent to ${\displaystyle T_{i}}$ while maintaining the original degree sequence ${\displaystyle A}$ of ${\displaystyle G}$. Thus any vertex not connected to ${\displaystyle S}$ can be connected to ${\displaystyle S}$ using the above method, and then we have the first case once more, through which we can obtain the degree sequence ${\displaystyle A'}$. Hence, ${\displaystyle A}$ is graphic if and only if ${\displaystyle A'}$ is also graphic.

Examples

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.

See also

• Erdős–Gallai theorem

Notes

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

References

• Havel, Václav (1955), "A remark on the existence of finite graphs", Časopis pro pěstování matematiky (in Czech), 80 (4): 477–480, doi:10.21136/CPM.1955.108220
• 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 (3): 496–506, doi:10.1137/0110037, 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.

• Graph algorithms