What Is the Havel‑Hakimi Algorithm?

The Havel‑HHakimi algorithm is a classical graph‑theoretic method that determines whether a given sequence of non‑negative integers can be realized as the degree sequence of a simple undirected graph. In network modeling, the degree sequence—a list of the number of edges incident to each node—is one of the most fundamental properties of a network. Knowing whether a sequence is graphical (i.e., realizable) is essential for validating network models, generating synthetic networks with prescribed properties, and understanding the structural constraints of real‑world systems.

The algorithm is elegantly simple: it repeatedly removes the largest degree and reduces the degrees of its neighbors, checking for contradictions along the way. Despite its simplicity, the Havel‑Hakimi algorithm is a cornerstone of graph theory and remains widely used in fields ranging from social network analysis to systems biology.

Historical Background

The algorithm was independently discovered by Václav Havel in 1955 and by S. Louis Hakimi in 1962. Havel published his result in a Czech mathematical journal, while Hakimi’s work appeared in the context of switching circuit theory. Both researchers recognized that verifying the realizability of a degree sequence is crucial for designing networks with desired connectivity patterns. The algorithm is sometimes called the Havel‑Hakimi theorem because it provides both a necessary and a sufficient condition for a sequence to be graphical.

Formal Definition and Algorithm Steps

Degree Sequence

A degree sequence \(d = (d_1, d_2, \dots, d_n)\) is a list of non‑negative integers sorted in non‑increasing order. For an undirected simple graph (no loops, no multiple edges), each integer represents the degree of a vertex. The sequence is graphical if there exists a simple graph whose vertices have exactly those degrees.

The Algorithm

Given a sequence \(d\) sorted in non‑increasing order:

  1. If the first element \(d_1\) is greater than the number of remaining elements minus 1, the sequence is not graphical (immediate failure).
  2. Remove \(d_1\) and subtract 1 from the next \(d_1\) elements in the sequence.
  3. Sort the resulting list in non‑increasing order again.
  4. Repeat steps 1–3 until either all elements become zero (sequence is graphical) or a negative number appears (sequence is not graphical).

If the process terminates with exactly \(n\) zeros, the degree sequence is realizable.

Proof Sketch

The algorithm is constructive: it can be used to build a graph that realizes the sequence. The key idea is that if a sequence is graphical, then there exists a graph where the vertex with the highest degree is connected to the next \(d_1\) highest‑degree vertices. This “greedy” connection pattern does not lose generality because any correct realization can be transformed into one of this form through edge swaps (a classic lemma of Hakimi). The algorithm therefore reduces the problem to a smaller subsequence, and by induction the condition becomes both necessary and sufficient. The formal proof relies on the Erdős–Gallai theorem, which gives an alternative characterization but is more complex to check computationally.

Complexity and Implementation

Naïve Implementation

A straightforward implementation sorts the sequence \(O(n \log n)\) each iteration, leading to \(O(n^2 \log n)\) worst‑case complexity. This is acceptable for small to medium networks (e.g., thousands of vertices).

Efficient Variants

By using a bucket or counting sort (since degrees are bounded by \(n-1\)), the sorting step can be reduced to \(O(n)\) per iteration, giving \(O(n^2)\) overall. In practice, many sequences become trivial after a few rounds, so the average performance is much better. The algorithm can also be implemented without explicit sorting at every step by maintaining a priority queue.

Python Example

def havel_hakimi(deg_seq):
    seq = sorted(deg_seq, reverse=True)
    while seq and seq[0] > 0:
        d = seq.pop(0)
        if d > len(seq):
            return False
        for i in range(d):
            seq[i] -= 1
            if seq[i] < 0:
                return False
        seq.sort(reverse=True)
    return all(v == 0 for v in seq)

This function returns True if the sequence is graphical, False otherwise. Note the early exit when the highest degree exceeds the remaining vertex count.

Examples

Graphical Sequence

Sequence: 3, 3, 2, 2, 2

  1. Sorted: 3,3,2,2,2. Remove 3, subtract 1 from next 3 → 2,1,1,2 → sort → 2,2,1,1
  2. Remove 2, subtract 1 from next 2 → 1,0,1 → sort → 1,1,0
  3. Remove 1, subtract 1 from next 1 → 0,0 → all zeros → graphical.

Indeed, a graph with five vertices (two of degree 3, three of degree 2) exists (e.g., a 5‑cycle with two chords).

Non‑graphical Sequence

Sequence: 4, 2, 2, 2, 1

  1. Sorted: 4,2,2,2,1. Remove 4, but only 4 remaining vertices –> immediate failure because 4 > 4? Actually, after removal there are 4 vertices, so 4 is allowed. Subtract 1 from next 4: 1,1,1,0 → sorted 1,1,1,0
  2. Remove 1, subtract 1 from next 1: 0,1,0 → sorted 1,0,0
  3. Remove 1, subtract 1 from next 1: -1,0 → negative → not graphical.

No simple graph can have that degree sequence.

Applications in Network Modeling

Validating Network Data

When collecting degree sequence data from real networks (e.g., social media followers, protein‑protein interactions), the Havel‑Hakimi algorithm can quickly check whether the observed sequence could possibly come from a simple graph. If not, it suggests measurement errors or the presence of multiple edges or self‑loops that should be accounted for.

Generating Synthetic Networks

Many generative models require a degree sequence as input. The algorithm is used to verify that a proposed sequence is graphical before running a configuration‑model algorithm (e.g., the Chung‑Lu or Molloy‑Reed methods). This prevents wasted computation and ensures that the synthetic network is physically realizable.

Designing Robust Topologies

Engineers designing communication networks (e.g., data centers, mesh networks) often want a specific degree distribution for fault tolerance. The Havel‑Hakimi algorithm helps determine whether a target distribution can be achieved with a simple graph, guiding the design process.

Limitations and Extensions

Scope of the Algorithm

The Havel‑Hakimi algorithm applies only to simple, undirected graphs. Directed graphs, multigraphs, and graphs with self‑loops require different criteria. For undirected multigraphs, the condition is simpler: the sum of degrees must be even. For directed graphs, the Gale‑Shapley or Fulkerson‑Chen theorems provide analogous tests.

Relation to the Erdős–Gallai Theorem

The Erdős–Gallai theorem provides an alternative characterization: a non‑increasing sequence \(d_1 \ge \dots \ge d_n\) is graphical if and only if the sum of degrees is even and for every \(k = 1,\dots,n\), the inequality \(\sum_{i=1}^k d_i \le k(k-1) + \sum_{i=k+1}^n \min(d_i, k)\) holds. While computationally heavier (\(O(n^2)\)), it gives more insight into the structure. The Havel‑Hakimi algorithm is a subroutine in many proofs of the Erdős–Gallai theorem.

Performance for Very Large Networks

For networks with millions of vertices, the iterative sorting becomes impractical. However, the algorithm is rarely needed at that scale; typically, one works with degree distributions rather than exact sequences. When exact verification is required, a divide‑and‑conquer version or an optimized bucket approach can handle sequences up to about 100,000 vertices in a few seconds.

Generalizations

Variants of the algorithm exist for bipartite graphs (the Gale‑Havel‑Hakimi algorithm) and for sequences that require a prescribed number of edges between partitions. These are used in modeling bipartite networks such as user‑item graphs or gene‑disease associations.

Practical Implementation Tips

  • Always sort the sequence at the start and after every reduction. Use Python’s built‑in sort() for clarity; for performance, consider implementing a counting sort if degrees are small integers.
  • Check for parity: the sum of all degrees must be even. While the algorithm implicitly checks this, an early parity check can save computation.
  • Handle isolated vertices (degree zero) gracefully; they do not affect the algorithm but must be present in the final zero‑check.
  • Use list comprehensions and in‑place modifications to avoid excessive memory allocation.
  • For repeated calls on many sequences (e.g., in a Monte Carlo simulation), pre‑compute common subroutines or use vectorized operations with NumPy if the sequence lengths are identical.

External Resources

For a deeper understanding, refer to the following authoritative sources:

Conclusion

The Havel‑Hakimi algorithm remains an indispensable tool for anyone working with network degree sequences. Its simplicity belies its power: in a few lines of code, it can validate the feasibility of a network structure, guide synthetic graph generation, and uncover measurement artifacts in empirical data. Whether you are a graph theorist, a network scientist, or a software engineer designing robust communication systems, mastering this algorithm equips you with a foundational check for graph realizability. By understanding its steps, complexity, and limitations, you can apply it confidently in both analytical and computational settings.