Havel–Hakimi Degree Sequences
Peel a degree sequence to construct a graph or expose an impossibility.
Free theory articlePeel a degree sequence to construct a graph or expose an impossibility.
Concept & interpretation
The Havel-Hakimi algorithm is a greedy algorithm to determine whether a given finite sequence of nonnegative integers can be realized as the degree sequence of a simple undirected graph. If it can, the sequence is called graphical.
Experiment
Interact with the module here: https://riano.app/module/havel-hakimi-degree-sequences
- Change the Degrees control to "Impossible". Notice how the algorithm steps through and halts, reporting that it is not graphical.
- Observe the Graphical output card updating based on the sequence's validity.