Havel-Hakimi Algorithm

A Bit of History

Václav Havel, a Czech mathematician, first proved this characterization in 1955. Seven years later, working independently in the United States, S. Louis Hakimi rediscovered the same result in a 1962 paper — another entry in this series' recurring pattern of near-simultaneous independent discovery (alongside Prim/Dijkstra, Ford-Fulkerson/Dinitz, and Erdős–Rényi/Gilbert). The algorithm answers a foundational question quietly assumed throughout this entire series: given a proposed list of vertex degrees, does any simple graph actually realize it?

Working Principle

A sequence of non-negative integers is called graphical if some simple graph exists whose vertex degrees are exactly that sequence. The Havel-Hakimi algorithm both tests graphicality and constructs a realizing graph if one exists, via a simple greedy recursive rule:

1. Sort the degree sequence in non-increasing order.
2. Take the largest degree \(d_1\), and connect that vertex to the next \(d_1\) highest-degree vertices in the sorted sequence, decreasing each of their degrees by 1.
3. Remove the now-satisfied first vertex (its degree requirement is fully met) and repeat on the remaining sequence.
4. If at any point a negative degree would result, or there are fewer than \(d_1\) remaining vertices to connect to, the sequence is not graphical. If the process terminates with all zeros, the sequence is graphical, and the edges chosen along the way form a valid realization.

Worked Example

Test the sequence \((3, 3, 2, 2, 2)\): sorted, take the first vertex (degree 3) and connect it to the next 3 highest-degree vertices, reducing them: \((3,3,2,2,2) \to (2,1,1,2)\) [connecting vertex 1 to vertices 2, 3, 4]. Re-sort: \((2,2,1,1)\). Take the first (degree 2), connect to the next 2: \((2,2,1,1) \to (1,0,1)\). Re-sort: \((1,1,0)\). Take the first (degree 1), connect to the next 1: \((1,1,0) \to (0,0)\). All zeros remain — the sequence is graphical, and the specific edges chosen along the way constitute one valid realizing graph.

Correctness

The correctness proof rests on a key exchange lemma: if a degree sequence is graphical at all, then it is graphical specifically by a graph where the highest-degree vertex connects to some \(d_1\) other highest-degree vertices (rather than some arbitrary lower-degree combination) — because any graph realizing the sequence can always be modified, via a careful edge-swapping argument, into one with this "greedy" connection pattern without changing any vertex's degree. This guarantees the greedy choice at each step never eliminates a valid solution that might have existed with a different choice.

Complexity Analysis

Each of the \(n\) steps requires re-sorting (or using a priority queue) over the remaining sequence:

$$\text{Time: } O(n^2) \qquad \text{(naive re-sorting each step)} \qquad O(n \log n) \text{ (with a priority queue)}$$

where \(n\) is the number of vertices — efficient enough to validate degree sequences even for reasonably large synthetic network-generation tasks.

Implementation

def havel_hakimi(degrees):
    """
    degrees: list of non-negative integers (a candidate degree sequence).
    Returns True if graphical, False otherwise.
    """
    seq = [(d, i) for i, d in enumerate(degrees)]  # keep original vertex labels

    while True:
        seq.sort(key=lambda x: -x[0])
        if seq[0][0] == 0:
            return True  # all zeros: graphical
        d, v = seq[0]
        rest = seq[1:]
        if d > len(rest):
            return False  # not enough remaining vertices to connect to
        for i in range(d):
            deg, label = rest[i]
            if deg - 1 < 0:
                return False
            rest[i] = (deg - 1, label)
        seq = rest

sequence = [3, 3, 2, 2, 2]
print(havel_hakimi(sequence))  # True

not_graphical = [4, 4, 1, 1]
print(havel_hakimi(not_graphical))  # False

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool havelHakimi(vector<int> degrees) {
    while (true) {
        sort(degrees.begin(), degrees.end(), greater<int>());
        if (degrees.empty() || degrees[0] == 0) return true;

        int d = degrees[0];
        vector<int> rest(degrees.begin() + 1, degrees.end());
        if (d > (int)rest.size()) return false;

        for (int i = 0; i < d; i++) {
            rest[i]--;
            if (rest[i] < 0) return false;
        }
        degrees = rest;
    }
}

int main() {
    vector<int> sequence = {3, 3, 2, 2, 2};
    cout << (havelHakimi(sequence) ? "graphical" : "not graphical") << endl;

    vector<int> notGraphical = {4, 4, 1, 1};
    cout << (havelHakimi(notGraphical) ? "graphical" : "not graphical") << endl;
    return 0;
}

import java.util.*;

class HavelHakimi {
    static boolean isGraphical(List<Integer> degrees) {
        List<Integer> seq = new ArrayList<>(degrees);
        while (true) {
            seq.sort(Collections.reverseOrder());
            if (seq.isEmpty() || seq.get(0) == 0) return true;

            int d = seq.get(0);
            List<Integer> rest = new ArrayList<>(seq.subList(1, seq.size()));
            if (d > rest.size()) return false;

            for (int i = 0; i < d; i++) {
                int val = rest.get(i) - 1;
                if (val < 0) return false;
                rest.set(i, val);
            }
            seq = rest;
        }
    }

    public static void main(String[] args) {
        System.out.println(isGraphical(Arrays.asList(3, 3, 2, 2, 2)));  // true
        System.out.println(isGraphical(Arrays.asList(4, 4, 1, 1)));      // false
    }
}

Real-World Applications

Exercises

1. Trace through the worked example by hand, drawing the actual graph constructed at each step.
2. Verify that the sequence \((4, 4, 1, 1)\) is not graphical using the algorithm, and explain in your own words why it fails.
3. Explain why any graphical sequence must have an even sum (connect this to the Handshake Lemma from Part 4), and use this as a quick pre-check before running the full algorithm.
4. Challenge: Modify the implementation to explicitly construct and print the adjacency list of a realizing graph, not just answer true/false.

Limitations