What am I proving with the Havel-Hakimi theorem?

$\begingroup$

Honestly,

Right now, I have no clue. Google gives me very abstract and vague definitions, and I have no idea what my goal is when I need to use the Havel-Hakimi theorem. Do I need to check if everything in the sequence is a zero like [0,0,0]? What if it's [1,0,0], isn't this graphical then?

The thing is, a graphical graph is not explained properly. What is that at all? A simple graph?

So, could someone please explain in plain English what it means to:

1. Have a graphical graph

2. How / When I can prove if it's graphical when using Havel-Hakimi theorem (should I get all zeros and solely zeros?)

$\endgroup$

1 Answer

$\begingroup$

A graph is not a thing that can be graphical. A sequence such as $(5,3,3,3,2,2,1,1)$ is graphical if and only if there is a simple graph whose vertices have that degree sequence. In this case, it is, because the graph

has this degree sequence: it has a vertex with degree $5$, three vertices with degree $3$, two vertices with degree $2$, and two vertices with degree $1$.

The Havel–Hakimi theorem says that we can test if a sequence is graphical by the following procedure:

1. Sort the sequence in decreasing order.

2. If the first term is $k$,

   • remove the first term,
   • subtract $1$ from the $k$ following terms.
3. If a negative number is obtained, stop. Otherwise, repeat from step 1.

In this example, from $(5,3,3,3,2,2,1,1)$ we:

1. Remove $5$ and then subtract $1$ from the next five terms to get $(2,2,2,1,1,1,1)$,
2. Remove $2$ and then subtract $1$ from the next two terms to get $(1,1,1,1,1,1)$,
3. Remove $1$ and then subtract $1$ from the next term to get $(0,1,1,1,1)$; sort to get $(1,1,1,1,0)$.
4. Remove $1$ and then subtract $1$ from the next term to get $(0,1,1,0)$; sort to get $(1,1,0,0)$.
5. Remove $1$ and then subtract $1$ from the next term to get $(0,0,0)$.
6. This is clearly graphical (it corresponds to a graph on $3$ vertices and no edges) so we can stop here.

We can stop when we get all zeroes, or earlier if becomes obvious that a sequence is graphical. For example, we could stop at $(1,1,1,1,1,1)$ by realizing that a graph with $6$ vertices connected by $3$ disjoint edges has this degree sequence.

In the case of a sequence such as $(1,0,0)$, we don't stop, so the next step is to remove $1$ and then subtract from the next term to get $(-1,0)$. This contains a negative number, so the sequence is not graphical.

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy