# What am I proving with the Havel-Hakimi theorem?

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?)

## 1 Answer

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.

• Thank you, but I don't understand the stopping at (1,1,1,1,1,1). How do you know I could stop there? – Siyah Apr 22 '17 at 14:55
• If you're not sure, you can always keep going. You can stop there if you can see that a graph with the degree sequence $(1,1,1,1,1,1)$ exists: the graph with vertices $\{a,b,c,d,e,f\}$ and edges $ab$, $cd$, $ef$. – Misha Lavrov Apr 22 '17 at 15:04