Topics: Graph Theory

The Havel-Hakimi algorithm is an algorithm that lets us know if there exists a simple graph whose degree sequence is a given non-increasing sequence of non-negative integers.

The algorithm consists of the following steps:

  1. Take the first greatest integer. Let be this value.
  2. Remove from the sequence
  3. Subtract from the next integers.
  4. Reorder the sequence so that it is non-increasing again.
  5. Repeat steps 1 through 4 until we reach a sequence that consists of all zeroes or we get a negative integer.

When the resulting sequence consists of all zeroes, the sequence corresponds to a simple graph and we say that it is a graphic sequence. Otherwise, the sequence doesn’t correspond to a simple graph and we say that it is non-graphic.