6
$\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$
8
$\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

533322111

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$
  • $\begingroup$ Thank you, but I don't understand the stopping at (1,1,1,1,1,1). How do you know I could stop there? $\endgroup$ – Siyah Apr 22 '17 at 14:55
  • 1
    $\begingroup$ 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$. $\endgroup$ – Misha Lavrov Apr 22 '17 at 15:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.