Havel–Hakimi algorithm

Template:Short description Template:No footnotes 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 Template:Harvtxt, and later by Template:Harvtxt.

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}}, \dots, {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 ${S, D_{j}}$ and ${T_{i}, W}$ , and adding the edges ${S, T_{i}}$ and ${W, D_{j}}$ . 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.

Notes

Template:Reflist

References

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

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

[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]

Havel–Hakimi algorithm

Contents

The algorithm

Proof

Examples

See also

Notes

References

Navigation menu

Havel–Hakimi algorithm

The algorithm

Proof

Examples

See also

Notes

References

Navigation menu

Search