How to Learn Havel–Hakimi: Degree Sequences, Graphicality, Greedy Realisation and Constructive Graph Theory

Wait, What?

A list of numbers can tell you whether a simple graph exists—even before you draw a single edge.

Suppose someone gives you the degree sequence 3,3,2,2,2 and asks: can five vertices be connected by a simple undirected graph so that their degrees are exactly those numbers? Havel–Hakimi answers the question constructively by repeatedly satisfying the highest remaining degree and reducing the problem.

For learners, it is a beautiful introduction to constructive graph theory because a greedy-looking step is backed by a theorem. It connects degree, simple graphs, invariants, feasibility, proof by exchange, graph construction and the important professional habit of checking problem assumptions before trusting an algorithm.

Quick Answer

Learn Havel–Hakimi in this order: vertex degree → degree sequence → simple graph rules → quick impossibility checks → sort descending → remove largest degree d → subtract 1 from the next d entries → repeat → detect failure or reach all zeros → reconstruct edges → compare with Erdős–Gallai and production implementations.

1. What Does “Graphical” Mean?

A finite sequence of nonnegative integers is called graphical if there exists a finite simple undirected graph whose vertex degrees are exactly those values.

“Simple” matters:

no self-loops;
no multiple edges between the same pair of vertices;
undirected edges;
every degree is therefore at most n−1 for n vertices.

2. Start With Cheap Necessary Checks

Before running the full reduction, reject obvious impossibilities:

any degree is negative;
any degree is greater than n−1;
the sum of degrees is odd.

The parity test follows from the handshaking lemma: every undirected edge contributes exactly two to the total degree sum.

These checks are necessary but not sufficient. An even sum does not guarantee graphicality.

3. The Havel–Hakimi Reduction

Sort the sequence in nonincreasing order:

d1 >= d2 >= ... >= dn

Remove d1. Then subtract one from the next d1 entries.

The theorem says the original sequence is graphical if and only if the reduced sequence is graphical, provided the reduction is legal.

4. Why the Greedy Step Makes Sense

If one vertex needs degree d1, it must be connected to d1 other vertices. Havel–Hakimi says we may choose the d1 vertices with the largest remaining degree requirements.

This is not just a heuristic. If some valid graph connects the highest-degree vertex differently, an edge-switching argument can transform that graph so the vertex connects to the highest-demand vertices without changing the degree sequence.

That exchange idea is the proof engine behind the greedy choice.

5. Work the Sequence 3,3,2,2,2

Start:

3,3,2,2,2

Remove the first 3 and subtract one from the next three entries:

3,2,2,2 -> 2,1,1,2 -> sort -> 2,2,1,1

Repeat:

2,2,1,1
remove 2 -> 2,1,1 -> 1,0,1 -> sort -> 1,1,0

1,1,0
remove 1 -> 1,0 -> 0,0

All zeros means the sequence is graphical.

6. Failure Can Happen in Several Ways

Suppose the largest degree is d, but fewer than d entries remain. Failure is immediate: that vertex cannot connect to enough distinct vertices.

If subtraction creates a negative degree, failure is also immediate. A negative remaining requirement means the greedy vertex would need to connect to a vertex that had no degree capacity left.

7. The Algorithm Can Construct a Graph, Not Just Say Yes

To build an actual graph, keep vertex labels attached to the degree requirements.

(degree, vertex_id)

When the current highest-degree vertex u has requirement d, connect u to the d vertices with highest remaining requirements. Then decrement those requirements and repeat.

At the end, the recorded edges form one valid realisation.

8. One Degree Sequence Can Have Many Realisations

Havel–Hakimi constructs a graph, not necessarily the only graph. Different tie-breaking choices among equal-degree vertices can produce different edge sets while preserving the same degree sequence.

This is a useful distinction between:

existence: does any graph realise the sequence?
construction: produce one such graph;
enumeration: find all non-isomorphic realisations;
sampling: generate a random realisation under some distribution.

Havel–Hakimi directly addresses the first two, not the last two.

9. The Sum of Degrees Gives the Edge Count

If a sequence is graphical, every realisation has:

|E| = (sum of degrees) / 2

For 3,3,2,2,2, the sum is 12, so every realisation has six edges.

This is a useful verification check after construction.

10. Havel–Hakimi Is a Decision Procedure and a Proof Technique

The repeated equivalence gives more than code. It gives a recursive proof strategy: reduce the original graphicality problem to a smaller one while preserving truth.

That pattern appears across algorithms:

reduce to a smaller instance;
prove the reduction preserves feasibility;
detect a base case;
reconstruct a solution if needed.

11. A Clear Pseudocode Version

is_graphical(degrees):
    while true:
        remove zeros
        if degrees is empty:
            return true

        sort degrees descending
        d = remove first degree

        if d  len(degrees):
            return false

        for i from 0 to d-1:
            degrees[i] -= 1
            if degrees[i] < 0:
                return false

For a constructor, store vertex IDs and record each selected edge before decrementing the neighbours.

12. Complexity Depends on How You Maintain Order

The simplest implementation sorts after every reduction. That is easy to understand and often perfectly adequate for moderate n.

More sophisticated implementations can avoid full re-sorting by using degree buckets, counting techniques or priority-oriented structures, especially when degrees are bounded. The professional question is whether the extra implementation complexity improves the actual workload.

13. Havel–Hakimi Versus Erdős–Gallai

Erdős–Gallai gives a characterisation of graphical sequences using a family of inequalities. Havel–Hakimi gives a recursive constructive reduction.

A useful mental split is:

Erdős–Gallai: inequality-based graphicality test;
Havel–Hakimi: greedy reduction that naturally constructs a realisation.

Modern libraries may offer both approaches because checking and constructing are related but not identical jobs.

14. The Result Depends on the Graph Model

Do not apply the simple undirected Havel–Hakimi rule unchanged to:

directed graphs with in-degree/out-degree pairs;
bipartite degree sequences;
multigraphs where parallel edges are allowed;
graphs with forbidden edges;
hypergraphs.

There are extensions and related algorithms for some of these models, but the theorem and reduction must match the exact graph type.

15. Common Failure States

Forgetting to sort before choosing the next largest requirement.
Dropping vertex labels when a concrete graph must be reconstructed.
Treating an even degree sum as sufficient for graphicality.
Allowing a vertex to connect to itself.
Creating duplicate edges in a supposedly simple graph.
Using the undirected algorithm for directed degree pairs.
Assuming the constructed graph is uniformly random among all realisations.

16. Build Tests Around Theorems

Good tests include:

all zeros;
a single nonzero degree;
complete graph sequence n−1 repeated n times;
path and cycle degree sequences;
odd total degree sum;
a degree greater than n−1;
known nongraphical sequences;
random graphs converted to degree sequences, which must be accepted.

For constructed outputs, verify every requested vertex degree exactly and assert no loops or duplicate undirected edges.

17. Practice Ladder: Beginner to Professional

Beginner: count vertex degrees from small drawn graphs.
Foundation: decide whether obvious sequences fail the parity or maximum-degree checks.
Intermediate: perform Havel–Hakimi reductions by hand and explain every subtraction.
Advanced: preserve vertex IDs and construct an explicit edge set.
Professional: compare Havel–Hakimi and Erdős–Gallai, analyse tie handling, use a maintained graph library, and distinguish deterministic construction from random realisation sampling.
Transfer: explain why a greedy step becomes trustworthy only after a proof that it preserves feasibility.

18. A Better Way to Study This Algorithm

Use a three-column trace: sorted sequence → chosen high-degree vertex → reduced sequence. Before performing each reduction, predict whether the next step will remain legal. Then reconstruct the actual edges from the same trace.

This fits evidence from programming education that prediction, tracing and worked-example fading can help learners build algorithmic schemas before full code writing. A useful Parsons exercise gives the steps “sort, remove, validate d, decrement next d, detect negative, repeat” in shuffled order and asks the learner to restore the invariant-preserving sequence.

Learning Hall Boundary

This article owns Havel–Hakimi for graphical degree sequences and constructive realisation of finite simple undirected graphs. It complements broader graph-algorithm material and does not replace existing graph traversal, matching, flow, clique or optimisation articles. It does not take over MindOS, Bolt or Student/Studying Interface canonical jobs.

Evidence Boundary

The modern NetworkX 3.6 documentation describes its maintained Havel–Hakimi graph constructor and cites S. L. Hakimi’s 1962 SIAM paper: NetworkX documentation. The directed-graph extension by Péter L. Erdős, István Miklós and Zoltán Toroczkai demonstrates how the same constructive idea changes when the graph model changes: Electronic Journal of Combinatorics. The learning design also draws on PRIMM, Parsons-problem research, subgoal-labelled worked examples and code-tracing studies in computing education.

Professional rule: you understand Havel–Hakimi when you can explain why the highest-degree greedy reduction preserves graphicality, reconstruct a valid simple graph with vertex identities intact, and state which graph models require a different theorem rather than a copied implementation.

Small Group Tutorials