Havel-Hakimi Algorithm

A Bit of History

Václav Havel established the reduction behind this algorithm in 1955, and S. Louis Hakimi independently published the same characterization in 1962. Their result answers a basic inverse problem: instead of reading degrees from a graph, start with desired degrees and ask whether any simple graph could have produced them.

The result is more than a yes-or-no theorem. If labels are retained during each reduction, the choices themselves construct a graph whose degree sequence is the input.

What Makes a Degree Sequence Graphical?

A finite sequence $(d_1,\ldots,d_n)$ is graphical if there exists a simple undirected graph on $n$ vertices whose vertex degrees are exactly those numbers. “Simple” imposes two constraints that shape the algorithm: no vertex can connect to itself, and no pair can receive more than one edge.

Labels are irrelevant for deciding graphicality but essential for construction. The sequences $(3,3,2,2,2)$ and any permutation of it pose the same decision problem; attaching labels $A,B,C,D,E$ lets us record which realization was built.

Fast Necessary Checks

These checks can reject many inputs immediately, but they are not sufficient. For example, $(3,3,1,1)$ stays within range and sums to $8$, yet it is not graphical. Havel–Hakimi detects the structural contradiction.

The Havel–Hakimi Reduction

Sort the sequence as $d_1\ge d_2\ge\cdots\ge d_n$. Then

$$ (d_1,d_2,\ldots,d_n)\text{ is graphical} $$

if and only if

$$ (d_2-1,\ldots,d_{d_1+1}-1,d_{d_1+2},\ldots,d_n)\text{ is graphical}. $$

1. Sort by remaining degree. Keep original vertex labels attached.
2. Remove the largest request $d$. That vertex must receive $d$ distinct neighbors.
3. Choose the next $d$ vertices. Record those edges and subtract one from each chosen residual degree.
4. Reject an impossible reduction. Fail if $d$ exceeds the number of remaining vertices or any chosen residual degree is already zero.
5. Repeat. All zeros certify a realization; every recorded edge belongs to it.

Visual Walkthrough

Label the sequence $(3,3,2,2,2)$ as $A{:}3,B{:}3,C{:}2,D{:}2,E{:}2$. Ties are broken alphabetically only to make the trace deterministic.

The Constructed Graph Is a Certificate

The recorded edges can be checked independently: they contain no loops or duplicates, and the incident-edge count at every labeled vertex matches the requested degree. A valid edge list is therefore a compact certificate that the sequence is graphical.

Why Connecting to the Largest Degrees Is Safe

One direction is immediate: if the reduced sequence has a realization, add a new vertex and connect it to the $d_1$ decremented vertices. Their degrees return to the original values.

The other direction uses an edge-switching argument. Suppose the original sequence has some realization, but the highest-degree vertex $v$ is adjacent to a lower-degree vertex $y$ and not to a higher-or-equal-degree vertex $x$ that the greedy rule prefers. Because $x$ has at least as many neighbors as $y$, there is a vertex $z$ adjacent to $x$ but not to $y$. Replace edges $vy$ and $xz$ by $vx$ and $yz$. No loop or duplicate edge is created, and all four degrees stay unchanged.

Repeating this two-edge switch transforms a valid realization until $v$ is connected to the desired $d_1$ highest-degree vertices. Deleting $v$ then realizes exactly the reduced sequence. Thus the greedy reduction is equivalent to the original problem, not merely a heuristic.

Complexity Analysis

The straightforward implementations below sort up to $n$ residual vertices in each of up to $n$ rounds:

$$\text{Time: }O(n^2\log n) \qquad \text{Space: }O(n+m),$$

where $m=\tfrac12\sum_i d_i$ is the number of constructed edges. A heap-based constructive version performs roughly one update per edge and costs $O((n+m)\log n)$. Degree buckets can improve performance when degrees are bounded. If only the decision is needed, the Erdős–Gallai inequalities can be checked in $O(n\log n)$ time after sorting, or faster with specialized implementations.

Implementation

Each version returns a decision, a realizing edge list when successful, and a short diagnostic when unsuccessful. Input labels are original indices; sorting never loses their identity.

def havel_hakimi(degrees):
    """Return (is_graphical, realizing_edges, diagnostic)."""
    n = len(degrees)
    if any(not isinstance(d, int) for d in degrees):
        return False, [], "degrees must be integers"
    if any(d < 0 or d >= n for d in degrees):
        return False, [], "a degree lies outside 0..n-1"
    if sum(degrees) % 2:
        return False, [], "degree sum is odd"

    remaining = [(degree, vertex) for vertex, degree in enumerate(degrees)]
    edges = []

    while remaining:
        remaining.sort(key=lambda item: (-item[0], item[1]))
        degree, vertex = remaining.pop(0)

        if degree == 0:
            return True, edges, "all residual degrees are zero"
        if degree > len(remaining):
            return False, [], f"vertex {vertex} needs too many neighbors"
        if any(remaining[i][0] == 0 for i in range(degree)):
            return False, [], f"vertex {vertex} would force a negative residual"

        for i in range(degree):
            neighbor_degree, neighbor = remaining[i]
            edges.append((vertex, neighbor))
            remaining[i] = (neighbor_degree - 1, neighbor)

    return True, edges, "empty sequence is graphical"


ok, edges, reason = havel_hakimi([3, 3, 2, 2, 2])
print(ok, edges)  # True; [(0,1), (0,2), (0,3), (1,4), (1,2), (3,4)]

ok, _, reason = havel_hakimi([3, 3, 1, 1])
print(ok, reason) # False; a positive residual would have to connect to zero

#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

struct Result {
    bool graphical;
    std::vector<std::pair<int, int>> edges;
    std::string diagnostic;
};

Result havelHakimi(const std::vector<int>& degrees) {
    const int n = static_cast<int>(degrees.size());
    long long degreeSum = 0;
    for (int d : degrees) {
        if (d < 0 || d >= n) return {false, {}, "degree outside 0..n-1"};
        degreeSum += d;
    }
    if (degreeSum % 2 != 0) return {false, {}, "degree sum is odd"};

    std::vector<std::pair<int, int>> remaining; // (residual, label)
    for (int v = 0; v < n; ++v) remaining.push_back({degrees[v], v});
    std::vector<std::pair<int, int>> edges;

    while (!remaining.empty()) {
        std::sort(remaining.begin(), remaining.end(), [](auto a, auto b) {
            return a.first != b.first ? a.first > b.first : a.second < b.second;
        });
        auto [degree, vertex] = remaining.front();
        remaining.erase(remaining.begin());

        if (degree == 0) return {true, edges, "all residual degrees are zero"};
        if (degree > static_cast<int>(remaining.size()))
            return {false, {}, "not enough remaining vertices"};

        for (int i = 0; i < degree; ++i) {
            if (remaining[i].first == 0)
                return {false, {}, "a decrement would become negative"};
            edges.push_back({vertex, remaining[i].second});
            --remaining[i].first;
        }
    }
    return {true, edges, "empty sequence is graphical"};
}

int main() {
    Result result = havelHakimi({3, 3, 2, 2, 2});
    std::cout << std::boolalpha << result.graphical
              << ", edges = " << result.edges.size() << '\n'; // true, 6
    std::cout << havelHakimi({3, 3, 1, 1}).graphical << '\n';      // false
}

import java.util.*;

public class HavelHakimi {
    static final class Item {
        int residual;
        final int vertex;
        Item(int residual, int vertex) {
            this.residual = residual;
            this.vertex = vertex;
        }
    }

    static final class Result {
        final boolean graphical;
        final List<int[]> edges;
        final String diagnostic;
        Result(boolean graphical, List<int[]> edges, String diagnostic) {
            this.graphical = graphical;
            this.edges = edges;
            this.diagnostic = diagnostic;
        }
    }

    static Result solve(List<Integer> degrees) {
        int n = degrees.size();
        long degreeSum = 0;
        for (int d : degrees) {
            if (d < 0 || d >= n)
                return new Result(false, List.of(), "degree outside 0..n-1");
            degreeSum += d;
        }
        if (degreeSum % 2 != 0)
            return new Result(false, List.of(), "degree sum is odd");

        List<Item> remaining = new ArrayList<>();
        for (int v = 0; v < n; v++) remaining.add(new Item(degrees.get(v), v));
        List<int[]> edges = new ArrayList<>();

        while (!remaining.isEmpty()) {
            remaining.sort(Comparator
                .comparingInt((Item item) -> item.residual).reversed()
                .thenComparingInt(item -> item.vertex));
            Item current = remaining.remove(0);

            if (current.residual == 0)
                return new Result(true, edges, "all residual degrees are zero");
            if (current.residual > remaining.size())
                return new Result(false, List.of(), "not enough remaining vertices");

            for (int i = 0; i < current.residual; i++) {
                Item neighbor = remaining.get(i);
                if (neighbor.residual == 0)
                    return new Result(false, List.of(), "a decrement would become negative");
                edges.add(new int[]{current.vertex, neighbor.vertex});
                neighbor.residual--;
            }
        }
        return new Result(true, edges, "empty sequence is graphical");
    }

    public static void main(String[] args) {
        Result result = solve(List.of(3, 3, 2, 2, 2));
        System.out.println(result.graphical + ", edges = " + result.edges.size()); // true, 6
        System.out.println(solve(List.of(3, 3, 1, 1)).graphical);                  // false
    }
}

Related Degree-Sequence Tools

Directed graphs require separate in-degree and out-degree criteria, while bipartite graphs require two degree sequences. Do not silently apply the simple undirected theorem to either setting.

Where the Algorithm Helps

Limitations and Common Pitfalls

Exercises