# Havel & Hakimi degree sequence theory

I'm currently starting a course about Graph Theory, and I've been explained about the Havel & Hakimi degree sequence. However, I'm not too sure about it yet. First of all, I want to know if I understand it correctly, so I'm going to try to explain what I think the theory proves.

First, I've shamelessly stolen the following statement from the presentation:

Okay, so what I want to ask is the following.

1. What does "is graphic" mean exactly. Does that mean it's a graph? I know stupid question, but I cannot think of a degree sequence that's not a graph...

2. What's the practical use of this. What problems could you solve with this.

• From degrees you can tell if the graph is Eulerian, you can tell if graph is a tree – Yaroslav Bulatov Feb 3 '11 at 19:12

1. I think the term is usually "graphical." It just means that $s^{*}$ is a sequence of degrees of the vertices of some graph $G$. So if you can create a graph with degrees from $s^{*}$ then you can create a graph with degrees from $s$ and vice versa. Note it doesn't mean that you create the same graph from $s$ and $s^{*}$. We just need to be able to create graphs from the sets of degrees (e.g. if $s$ is graphical, then we can create a graph $G$ from $s$ and a graph $G'$ from $s^{*}$).