Havel-Hakimi Theorem

In this tutorial, we will learn how to determine if a given degree sequence can form a simple graph using Havel-Hakimi theorem. A graph is said to be a simple graph if it has no self-loop and parallel edges. For a given graph, it is always possible to find its degree sequence, but it may or may not be possible to draw a graph for a given degree sequence. 

A degree sequence is called a graphic sequence if a simple graph can be drawn with that sequence. For example, the degree sequence <2, 2, 2> is graphic. 

Theorem: 

The nonincreasing sequence $<d_1, d_2, \ldots, d_n>$ is graphic if and only if the sequence $(d_2-1,d_3-1, \ldots, d_{d_1+1}-1, d_{d_1+2}, d_{d_1+3}, \ldots, d_n)$ is also graphic. 

Note: A sequence with all zeroes is always graphic because we can draw that many isolated vertices. 

Based on the above theorem, we can use the following algorithm to draw a simple graph from a given degree sequence of nonincreasing nonnegative numbers.  

Algorithm: 

1. Pick the vertex with the highest degree $d_1$.  
2. Connect this vertex to the next $d_1$ vertices. Now this vertex has been exhausted. 
3. Repeat steps 1 and 2 till all the vertices are exhausted. 
4. If all the vertices get exhausted, then the given sequence has reduced to all zeroes, and we conclude that the given sequence is graphic. If we end up with non-zero vertices that can't be exhausted further, then the given sequence is not graphic. 

Previous Post Next Post