Havel Hakimi Algorithm
- John Golden
The Havel Hakimi Algorithm is a reduction process to see if a degree sequence is the degree sequence of a simple graph. It is equivalent to removing the vertex with the highest degree, and docking that many other vertices 1 degree for the edges you're removing. See if you can figure out precisely what the algorithm is doing. If you reach all zeroes, it is graphical, since you can make an isolated graph with that number of vertices. Often you can tell before that, however, that the degree sequence could make a graph.