Construct Graph from a Degree Sequence (Havel-Hakimi)

Construct Graph from a Degree Sequence asks a deceptively deep question: given only how many edges each vertex should have, can a simple graph actually exist? The Havel-Hakimi algorithm answers it and builds the graph at the same time — a greedy peel-off that is far simpler than it sounds.

The slow way first

You could try to actually place edges by brute force: pick some pair of vertices that both still need edges, connect them, and backtrack whenever you get stuck. With n vertices there are O(n²) candidate edges and exponentially many ways to choose them, so naive search blows up fast. We want a rule that decides feasibility directly, without searching.

The question to ask: which vertex is the most constrained? The one demanding the most edges. If we can always satisfy the hungriest vertex greedily, we never need to backtrack.

The idea: satisfy the hungriest vertex first

Havel-Hakimi is one move repeated. Sort the degrees descending. Take the largest, d. That vertex must connect to d others — so greedily connect it to the next d highest-demand vertices and subtract 1 from each of their degrees (those subtractions are the edges). Drop the satisfied vertex, re-sort, and repeat.

Two stopping rules. If subtracting ever drives a degree below zero, that vertex needs more partners than exist — the sequence is not graphical. If instead everything reaches zero, every demand was met and the sequence is graphical.

Walk through it

Step through the animation with degrees = [2, 3, 2, 3, 2]. First it sorts to [3, 3, 2, 2, 2]. The pointer d marks the largest, 3; we subtract 1 from the next three cells, recording three edges. No value went negative, so we drop the used vertex, re-sort the remainder, and loop. Every round shrinks the list until all degrees are zero — confirming the graph exists.

Pseudocode

degrees = list(degrees)
loop:
    sort degrees in descending order
    d = remove the first (largest) degree
    if d == 0:
        return True            # everything satisfied
    subtract 1 from the next d degrees   # these become edges
    if any of those went below 0:
        return False           # impossible
    # loop continues on the smaller sequence

The Python solution

def is_graphical(degrees):
    degrees = list(degrees)
    while True:
        degrees.sort(reverse=True)
        d = degrees.pop(0)
        if d == 0:
            return True
        for i in range(d):
            degrees[i] -= 1
        if degrees[d - 1] < 0:
            return False

• We copy the input so we can mutate freely.
• Each pass sorts descending so the largest demand is at the front.
• degrees.pop(0) removes the hungriest vertex and gives us its demand d.
• If d == 0 the list is all zeros (sorted, the front is the max) — every vertex is satisfied, so the sequence is graphical.
• The for loop subtracts 1 from the next d entries — each subtraction is one edge from the popped vertex.
• If d exceeds the number of remaining vertices, or any of those entries goes negative, degrees[d - 1] < 0 catches it (an index error here also signals impossibility in a hardened version) and we return False.

Complexity

The list copy is O(n) extra space. Sorting every round is the cost; a counting-sort variant can shave the log factor, but the greedy peel-off is what makes the whole thing correct without backtracking.

When this pattern shows up

Practice