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.

How to tell if there exists a graph given degrees of vertices? Not sure how to go about this one

Is there a graph on $10$ vertices with degrees $1, 1, 3, 3, 6, 6, 6, 7, 8, 9$?

share|improve this question
3  
Are we allowing multiple edges between two vertices? Are we allowing edges that begin and end on the same vertex? –  Logan Nov 5 '12 at 5:14

2 Answers 2

up vote 11 down vote accepted

HINT: If there’s a vertex of degree $9$, it’s joined to each of the other vertices. If there’s also a vertex of degree $8$, it’s joined to all but one of the other vertices. Is it then possible to have two vertices of degree $1$?

share|improve this answer
    
that's great thank you –  kfem Nov 5 '12 at 5:33
    
@kfem: You’re welcome. –  Brian M. Scott Nov 5 '12 at 5:34

You can solve such problems with the Havel-Hakimi Theorem. The theorem states that either all the following degree sequences can be realized as a simple graph or none of them can. To get the next sequence in the list, remove the first element (call it $k$) and reduce the next $k$ elements by one (assuming always that the sequence is written in non-increasing order).

  • 9, 8, 7, 6, 6, 6, 3, 3, 1, 1
  • 7, 6, 5, 5, 5, 2, 2, 0, 0
  • 5, 4, 4, 4, 1, 1, -1, 0

We can go ahead and stop because no vertex can have degree of $-1$. By the theorem, your original sequence cannot be realized either.

share|improve this answer
3  
In fact, we could have stopped even at the second line. The first vertex has degree seven, but there are only six other vertices of positive degree. The nice thing about Havel-Hakimi is that you can carry the procedure until it is painfully obvious whether the graph can be realized or not. –  Austin Mohr Nov 5 '12 at 6:21

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.