Havel–Hakimi algorithm

Short description: Algorithm in graph theory

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 [math]\displaystyle{ A = (s, t_{1},..., t_{s}, d_{1},..., d_{n}) }[/math] be a finite list of nonnegative integers that is nonincreasing. Let [math]\displaystyle{ A' = (t_{1}-1,..., t_{s}-1, d_{1},..., d_{n}) }[/math] be a second finite list of nonnegative integers that is rearranged to be nonincreasing. List [math]\displaystyle{ A }[/math] is graphic if and only if list [math]\displaystyle{ A' }[/math] is graphic.

If the given list [math]\displaystyle{ A }[/math] is graphic, then the theorem will be applied at most [math]\displaystyle{ n-1 }[/math] times setting in each further step [math]\displaystyle{ A:=A' }[/math]. Note that it can be necessary to sort this list again. This process ends when the whole list [math]\displaystyle{ A' }[/math] consists of zeros. Let [math]\displaystyle{ G }[/math] be a simple graph with the degree sequence [math]\displaystyle{ A }[/math]: Let the vertex [math]\displaystyle{ S }[/math] have degree [math]\displaystyle{ s }[/math]; let the vertices [math]\displaystyle{ T_{1},..., T_{s} }[/math] have respective degrees [math]\displaystyle{ t_{1},..., t_{s} }[/math]; let the vertices [math]\displaystyle{ D_{1},..., D_{n} }[/math] have respective degrees [math]\displaystyle{ d_{1},..., d_{n} }[/math]. In each step of the algorithm, one constructs the edges of a graph with vertices [math]\displaystyle{ T_{1},..., T_{s} }[/math]—i.e., if it is possible to reduce the list [math]\displaystyle{ A }[/math] to [math]\displaystyle{ A' }[/math], then we add edges [math]\displaystyle{ \{S,T_1\},\{S,T_2\},\cdots,\{S,T_{s}\} }[/math]. When the list [math]\displaystyle{ A }[/math] cannot be reduced to a list [math]\displaystyle{ A' }[/math] of nonnegative integers in any step of this approach, the theorem proves that the list [math]\displaystyle{ A }[/math] 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 [math]\displaystyle{ A' }[/math] is graphic, and there exists a simple graph [math]\displaystyle{ G' }[/math] with the degree sequence [math]\displaystyle{ A' = (t_{1}-1,..., t_{s}-1, d_{1},..., d_{n}) }[/math]. Then we add a new vertex [math]\displaystyle{ v }[/math] adjacent to the [math]\displaystyle{ s }[/math] vertices with degrees [math]\displaystyle{ t_{1}-1,..., t_{s}-1 }[/math] to obtain the degree sequence [math]\displaystyle{ A }[/math].

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

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

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

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

Examples

Let [math]\displaystyle{ 6, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1 }[/math] 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, [math]\displaystyle{ 6 }[/math] —  and all its incident edges to get [math]\displaystyle{ 2, 2, 2, 2, 1, 1, 2, 2, 1, 1 }[/math] (assuming the vertex with highest degree is adjacent to the [math]\displaystyle{ 6 }[/math] vertices with next highest degree). We rearrange this sequence in nonincreasing order to get [math]\displaystyle{ 2, 2, 2, 2, 2, 2, 1, 1, 1, 1 }[/math]. We repeat the process, removing the vertex with the next highest degree to get [math]\displaystyle{ 1, 1, 2, 2, 2, 1, 1, 1, 1 }[/math] and rearranging to get [math]\displaystyle{ 2, 2, 2, 1, 1, 1, 1, 1, 1 }[/math]. We continue this removal to get [math]\displaystyle{ 1, 1, 1, 1, 1, 1, 1, 1 }[/math], and then [math]\displaystyle{ 0, 0, 0, 0, 0, 0, 0, 0 }[/math]. This sequence is clearly graphic, as it is the simple graph of [math]\displaystyle{ 8 }[/math] isolated vertices.

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

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

See also

• Erdős–Gallai theorem

References

• Havel, Václav (1955), "A remark on the existence of finite graphs" (in Czech), Časopis pro pěstování matematiky 80: 477–480, http://eudml.org/doc/19050 
• "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, 1962 .
• Shahriari, Shahriar (2022) (in English), Invitation to Combinatorics, Cambridge U. Press. 
• West, Douglas B. (2001). Introduction to graph theory. Second Edition. Prentice Hall, 2001. 45-46.