Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

2 Answers

up vote 5 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|improve this answer
    
I believe 2 isn't about degree sequences, but about Havel-Hakimi. –  Aryabhata Feb 3 '11 at 17:25
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.