Havel–Hakimi Degree Sequences

Worked Example

Consider the degree sequence [3, 3, 1, 1]. We apply the Havel-Hakimi algorithm step by step to determine if it is graphical:

1. Sort the sequence descending: [3, 3, 1, 1].
2. Remove the highest degree node (degree 3) and decrement the next 3 entries in the sequence.
3. The remaining entries [3, 1, 1] become [3-1, 1-1, 1-1] which equals [2, 0, 0].
4. Sort descending: [2, 0, 0].
5. Remove the highest degree node (degree 2) and attempt to decrement the next 2 entries.
6. The next 2 entries are both 0. Decrementing them yields [-1, -1].
7. Because negative degrees appear, the algorithm terminates. The sequence [3, 3, 1, 1] is not graphical.

Experiment

Interact with the module here: https://riano.app/module/havel-hakimi-degree-sequences

1. Change the Degrees control to "Impossible". Notice how the algorithm steps through and halts, reporting that it is not graphical.
2. Observe the Graphical output card updating based on the sequence's validity.

Limitations

The Havel-Hakimi algorithm provides a constructive proof for simple undirected graphs. It does not apply to directed graphs or multigraphs. Numerical limitations are not a primary concern here as degree sequences are strictly integral. A sequence with an odd sum is trivially rejected since every edge contributes exactly 2 to the total degree sum.

References

NetworkX algorithm documentation for graphical sequences: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.graphical.is_graphical.html