Havel–Hakimi algorithm explained

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, and later by .

The algorithm

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

Let

A = (s, t _{1} ,..., t _{s} , d _{1} ,..., d _{n} ) be a finite list of nonnegative integers that is nonincreasing. Let 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 A is graphic if and only if list A' is graphic.

If the given list

A is graphic, then the theorem will be applied at most n -1 times setting in each further step A: = A' . Note that it can be necessary to sort this list again. This process ends when the whole list A' consists of zeros. Let G be a simple graph with the degree sequence A : Let the vertex S have degree s ; let the vertices T _{1} ,..., T _{s} have respective degrees t _{1} ,..., t _{s} ; let the vertices D _{1} ,..., D _{n} have respective degrees d _{1} ,..., d _{n} . In each step of the algorithm, one constructs the edges of a graph with vertices T _{1} ,..., T _{s} —i.e., if it is possible to reduce the list A to A' , then we add edges \{S,T _{1\},\{S,T} _{2\}, … ,\{S,T} _{s} \} . When the list A cannot be reduced to a list A' of nonnegative integers in any step of this approach, the theorem proves that the list 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

A' is graphic, and there exists a simple graph G' with the degree sequence A' = (t _{1} -1 ,..., t _{s} -1 , d _{1} ,..., d _{n} ) . Then we add a new vertex v adjacent to the s vertices with degrees t _{1} -1 ,..., t _{s} -1 to obtain the degree sequence A .

To prove the other direction, assume that

A is graphic, and there exists a simple graph G with the degree sequence A = (s, t _{1} ,..., t _{s} , d _{1} ,..., d _{n} ) and vertices S, T _{1} ,..., T _{s} , D _{1} ,..., D _{n} . We do not know which s vertices are adjacent to S , so we have two possible cases.

In the first case,

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

In the second case,

S is not adjacent to some vertex T _{i} for some 1 \leq i \leq s in G . Then we can change the graph G so that S is adjacent to T _{i} while maintaining the same degree sequence A . Since S has degree s , the vertex S must be adjacent to some vertex D _{j} in G for 1 \leq j \leq n : Let the degree of D _{j} be d _{j} . We know t _{i} \geq d _{j} , as the degree sequence A is in non-increasing order.

Since

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

Examples

Let

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,

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

To show an example of a non-graphic sequence, let

6 , 5 , 5 , 4 , 3 , 2 , 1 be a nonincreasing, finite degree sequence of nonnegative integers. Applying the algorithm, we first remove the degree 6 vertex and all its incident edges to get 4 , 4 , 3 , 2 , 1 , 0 . Already, we know this degree sequence is not graphic, since it claims to have 6 vertices with one vertex not adjacent to any of the other vertices; thus, the maximum degree of the other vertices is 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 2 ; however, the sequence claims to have a vertex with degree 1 . Thus, the sequence is not graphic.

For the sake of the algorithm, if we were to reiterate the process, we would get

3 , 2 , 1 , 0 , 0 which is yet more clearly not graphic. One vertex claims to have a degree of 3 , and yet only two other vertices have neighbors. Thus the sequence cannot be graphic.

See also

• Erdős–Gallai theorem

References

• • .
  • West, Douglas B. (2001). Introduction to graph theory. Second Edition. Prentice Hall, 2001. 45-46.

Notes and References

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