The Havel-Hakimi Algorithm: Determining Graphical Sequences

One of the fundamental questions in graph theory is: Given a sequence of numbers, can we construct a graph where each vertex has exactly those degrees? This is called the graphical realization problem, and the Havel-Hakimi algorithm provides an elegant solution.

What is a Graphic Sequence?

A degree sequence is simply a list of numbers representing the degrees of vertices in a graph. For example, [3, 3, 2, 2, 2] represents a graph with 5 vertices where two vertices have degree 3 and three vertices have degree 2.

A degree sequence is called graphic (or graphical) if there exists at least one simple graph (no loops or multiple edges) that realizes it.

Quick Examples

Graphic sequences:
- [3, 3, 2, 2, 2] ✓ (Can form a graph)
- [4, 2, 2, 2, 2] ✓ (Can form a graph)
- [2, 2, 2, 2] ✓ (Forms a 4-cycle)

Non-graphic sequences:
- [5, 3, 2, 1] ✗ (Impossible - first vertex needs degree 5 but we only have 3 other vertices)
- [3, 3, 3, 1] ✗ (Cannot be realized)
- [3, 2, 1] ✗ (Sum is odd - impossible since each edge contributes 2 to the total degree)

The Havel-Hakimi Theorem

Before diving into the algorithm, let’s understand the beautiful theorem that powers it.

The Theorem Statement

Havel-Hakimi Theorem: A nonincreasing sequence $(d_1, d_2, ..., d_n)$ where $d_1 \geq d_2 \geq ... \geq d_n$ is graphic if and only if the sequence:

$$(d_2 - 1, d_3 - 1, ..., d_{d_1+1} - 1, d_{d_1+2}, d_{d_1+3}, ..., d_n)$$

is also graphic.

Understanding the Theorem

Let’s break down what this means:

1. Start with a sorted sequence (highest to lowest)
2. Take the first element $d_1$ (the highest degree)
3. Reduce the next $d_1$ elements by 1 (these are the vertices we connect to)
4. Keep the remaining elements unchanged
5. The original sequence is graphic ⟺ the new sequence is graphic

Why Does This Work?

The intuition is simple: If we have a vertex of degree $d_1$, it must connect to exactly $d_1$ other vertices. We might as well connect it to the $d_1$ vertices with the highest remaining degrees. Once we’ve “used up” this vertex, we can forget about it and check if the remaining degree sequence (with those connections accounted for) is graphic.

The Havel-Hakimi Algorithm

Now we can turn this theorem into a systematic algorithm:

Algorithm Steps

1. Sort the sequence in nonincreasing order
2. If all elements are 0, return TRUE (graphic)
3. If any element is negative, return FALSE (not graphic)
4. Remove the first element d₁
5. Subtract 1 from the next d₁ elements
6. If there aren't enough elements to subtract from, return FALSE
7. Go back to step 1 and repeat

Example 1: A Graphic Sequence

Let’s determine if [4, 3, 3, 2, 2] is graphic.

Step 1: Sequence is already sorted: [4, 3, 3, 2, 2]

Step 2: Not all zeros, continue

Step 3: Remove first element (4), subtract 1 from next 4 elements:
- Original: [4, 3, 3, 2, 2]
- After: [3-1, 3-1, 2-1, 2-1] = [2, 2, 1, 1]

Step 4: Sort: [2, 2, 1, 1] (already sorted)

Step 5: Remove first element (2), subtract 1 from next 2 elements:
- After: [2-1, 1-1, 1] = [1, 0, 1]

Step 6: Sort: [1, 1, 0]

Step 7: Remove first element (1), subtract 1 from next 1 element:
- After: [1-1, 0] = [0, 0]

Result: All zeros! ✓ The sequence IS graphic

Example 2: A Non-Graphic Sequence

Let’s check if [3, 3, 3, 1] is graphic.

Step 1: Already sorted: [3, 3, 3, 1]

Step 2: Remove first element (3), subtract 1 from next 3 elements:
- After: [3-1, 3-1, 1-1] = [2, 2, 0]

Step 3: Already sorted: [2, 2, 0]

Step 4: Remove first element (2), subtract 1 from next 2 elements:
- After: [2-1, 0-1] = [1, -1]

Result: We got a negative number! ✗ The sequence is NOT graphic

Example 3: Detailed Walkthrough with Graph Construction

Let’s work through [3, 3, 2, 2, 2] and actually construct the graph.

Initial sequence: [3, 3, 2, 2, 2]

Let’s label vertices as A, B, C, D, E with degrees:
- A: degree 3
- B: degree 3
- C: degree 2
- D: degree 2
- E: degree 2

Iteration 1:
- Take A (degree 3)
- Connect A to the next 3 highest: B, C, D
- Remaining degrees: B=2, C=1, D=1, E=2
- New sequence: [2, 2, 1, 1]

Iteration 2:
- Take B (degree 2 remaining)
- Connect B to next 2 highest: E, C
- Remaining degrees: C=0, D=1, E=1
- New sequence: [1, 1, 0]

Iteration 3:
- Take D (degree 1 remaining)
- Connect D to next 1 highest: E
- Remaining degrees: E=0, C=0
- New sequence: [0, 0]

Final Graph:
- A connects to: B, C, D
- B connects to: A, C, E
- C connects to: A, B
- D connects to: A, E
- E connects to: B, D

You can verify each vertex has the correct degree!

Interactive Example

Try running the Havel-Hakimi algorithm on this graph’s degree sequence yourself!

Common Edge Cases

Case 1: Odd Sum

If the sum of all degrees is odd, the sequence cannot be graphic. This is because each edge contributes exactly 2 to the sum of degrees (one for each endpoint).

Example: [3, 2, 1] → Sum = 6 (even) ✓ Could be graphic
Example: [3, 2, 2] → Sum = 7 (odd) ✗ Definitely not graphic

Case 2: Degree Too Large

If any degree $d_i > n - 1$ where $n$ is the number of vertices, it’s impossible (you can’t connect to more vertices than exist).

Example: [5, 2, 2, 1] → First vertex needs 5 connections but only 3 other vertices exist ✗

Case 3: All Zeros

A sequence of all zeros is always graphic - just draw that many isolated vertices!

Algorithm Complexity

The Havel-Hakimi algorithm has a time complexity of O(n²) where n is the length of the sequence:
- Each iteration processes one element: O(n) iterations
- Each iteration involves sorting: O(n log n)
- Overall: O(n² log n), but can be optimized to O(n²) with proper data structures

Why Is This Algorithm Useful?

1. Graph Realization: Determine if a degree sequence can be realized as a graph
2. Network Design: Verify if a proposed network topology is valid
3. Social Networks: Check if observed degree distributions are possible
4. Graph Reconstruction: Reconstruct graphs from partial information
5. Error Detection: Identify invalid data in graph datasets

Practical Applications

Social Network Analysis

Suppose you survey people asking “How many friends do you have?” You get: [5, 4, 4, 3, 3, 2]. Before building your network model, you can use Havel-Hakimi to verify this data is consistent with a possible friendship graph.

Network Design

When designing a computer network, you might specify how many connections each router should have. Havel-Hakimi helps verify your design is actually possible before purchasing hardware.

Graph Databases

When storing graphs in databases, degree sequences can be used as checksums. Havel-Hakimi helps validate data integrity.

Implementing the Algorithm

Here’s a simple implementation in Python:

def is_graphic(sequence):
    """Check if a degree sequence is graphic using Havel-Hakimi"""
    # Make a copy to avoid modifying original
    seq = sorted(sequence, reverse=True)

    while seq:
        # Remove trailing zeros
        seq = [d for d in seq if d != 0]

        # Empty or all zeros - graphic!
        if not seq:
            return True

        # Get the first element
        d = seq.pop(0)

        # Check if we have enough elements
        if d > len(seq):
            return False

        # Subtract 1 from the next d elements
        for i in range(d):
            seq[i] -= 1
            if seq[i] < 0:
                return False

        # Re-sort for next iteration
        seq.sort(reverse=True)

    return True

# Test it!
print(is_graphic([4, 3, 3, 2, 2]))  # True
print(is_graphic([3, 3, 3, 1]))     # False

Related Concepts

• Erdős–Gallai Theorem: Another method to test if a sequence is graphic
• Degree Sequence Problem: The general problem of graph realization
• Multigraphs: If we allow multiple edges, more sequences become graphic
• Directed Graphs: Similar algorithms exist for directed graphs with in-degrees and out-degrees

Summary

The Havel-Hakimi algorithm is a beautiful example of how a simple theorem can lead to an elegant and practical algorithm. Key takeaways:

✓ A degree sequence is graphic if you can draw a graph with those degrees
✓ The algorithm iteratively reduces the problem to simpler cases
✓ If you reach all zeros, the sequence is graphic
✓ If you get negative numbers or run out of vertices, it’s not graphic
✓ The algorithm not only tests but also guides construction of the graph

Understanding this algorithm deepens your intuition about graphs and provides a powerful tool for analyzing network structures!

Practice Problems

Try these sequences yourself:

1. [5, 4, 3, 2, 2, 2] - Graphic or not?
2. [6, 6, 5, 4, 3, 3, 1] - Graphic or not?
3. [4, 4, 4, 4, 2] - Graphic or not?
4. Construct a graph for any graphic sequence above!

Want to see the Havel-Hakimi algorithm in action? Use our interactive playground to construct graphs from degree sequences!