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:
Have a graphical graph
How / When I can prove if it's graphical when using
Havel-Hakimi theorem(should I get all zeros and solely zeros?)
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:
- Sort the sequence in decreasing order.
If the first term is $k$,
- remove the first term,
- subtract $1$ from the $k$ following terms.
- 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:
- Remove $5$ and then subtract $1$ from the next five terms to get $(2,2,2,1,1,1,1)$,
- Remove $2$ and then subtract $1$ from the next two terms to get $(1,1,1,1,1,1)$,
- 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)$.
- Remove $1$ and then subtract $1$ from the next term to get $(0,1,1,0)$; sort to get $(1,1,0,0)$.
- Remove $1$ and then subtract $1$ from the next term to get $(0,0,0)$.
- 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
