Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

enter image description here

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.

share|cite|improve this question
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
up vote 6 down vote accepted
  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^{*}$).

  2. It can be used to figure out whether two graphs are isomorphic. If the degree sequences of two graphs are different, then they can't be isomorphic.

share|cite|improve this answer
I believe 2 isn't about degree sequences, but about Havel-Hakimi. – Aryabhata Feb 3 '11 at 17:25

There is a nice treatment of the Havel-Hakimi theorem on pages 44-46 of Doug West's book, Introduction to Graph Theory (Second edition). As far as uses of this kind of result one might be using graph theory to model some physical molecule that one would want to construct. One first step might be to see if there is a graph with specified valences (degrees). Often one wants a graph with the specified valences and additional properties such as that the graph with these valences is a tree or can be embedded in the plane where the edges meet only at vertices. Many additional specialized results about "realizing" graphs with specific properties and specified valences have been found.

share|cite|improve this answer
  1. Graphic Sequence is only for simple graphs. It means that if a degree sequence is also a graphic sequence, the graph is simple.

  2. If you prove that a huge graph is a simple graph (using Havel & Hakimi) you can use the properties of simple graphs to select best algorithms to solve further problems on mentioned graph.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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