Havel–Hakimi algorithm
![]() | 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 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 be a finite list of nonnegative integers that is nonincreasing. Let be a second finite list of nonnegative integers that is rearranged to be nonincreasing. List is graphic if and only if list is graphic.
If the given list is graphic, then the theorem will be applied at most times setting in each further step . Note that it can be necessary to sort this list again. This process ends when the whole list consists of zeros. Let be a simple graph with the degree sequence : Let the vertex have degree ; let the vertices have respective degrees ; let the vertices have respective degrees . In each step of the algorithm, one constructs the edges of a graph with vertices —i.e., if it is possible to reduce the list to , then we add edges . When the list cannot be reduced to a list of nonnegative integers in any step of this approach, the theorem proves that the list 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 is graphic, and there exists a simple graph with the degree sequence . Then we add a new vertex adjacent to the vertices with degrees to obtain the degree sequence .
To prove the other direction, assume that is graphic, and there exists a simple graph with the degree sequence and vertices . We do not know which vertices are adjacent to , so we have two possible cases.
In the first case, is adjacent to the vertices in . In this case, we remove with all its incident edges to obtain the degree sequence .
In the second case, is not adjacent to some vertex for some in . Then we can change the graph so that is adjacent to while maintaining the same degree sequence . Since has degree , the vertex must be adjacent to some vertex in for : Let the degree of be . We know , as the degree sequence is in non-increasing order.
Since , we have two possibilities: Either , or . If , then by switching the places of the vertices and , we can adjust so that is adjacent to instead of If , then since is adjacent to more vertices than , let another vertex be adjacent to and not . Then we can adjust by removing the edges and , and adding the edges and . This modification preserves the degree sequence of , but the vertex is now adjacent to instead of . In this way, any vertex not connected to can be adjusted accordingly so that is adjacent to while maintaining the original degree sequence of . Thus any vertex not connected to can be connected to using the above method, and then we have the first case once more, through which we can obtain the degree sequence . Hence, is graphic if and only if is also graphic.
The time complexity of the algorithm is .
Examples[]
Let 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, — and all its incident edges to get (assuming the vertex with highest degree is adjacent to the vertices with next highest degree). We rearrange this sequence in nonincreasing order to get . We repeat the process, removing the vertex with the next highest degree to get and rearranging to get . We continue this removal to get , and then . This sequence is clearly graphic, as it is the simple graph of isolated vertices.
To show an example of a non-graphic sequence, let be a nonincreasing, finite degree sequence of nonnegative integers. Applying the algorithm, we first remove the degree vertex and all its incident edges to get . Already, we know this degree sequence is not graphic, since it claims to have vertices with one vertex not adjacent to any of the other vertices; thus, the maximum degree of the other vertices is . 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 ; however, the sequence claims to have a vertex with degree . Thus, the sequence is not graphic.
For the sake of the algorithm, if we were to reiterate the process, we would get which is yet more clearly not graphic. One vertex claims to have a degree of , and yet only two other vertices have neighbors. Thus the sequence cannot be graphic.
See also[]
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.
- Graph algorithms