3
$\begingroup$

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$?

  • 3
    Are we allowing multiple edges between two vertices? Are we allowing edges that begin and end on the same vertex?2012-11-05

2 Answers 2

11

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$?

  • 0
    @kfem: You’re welcome.2012-11-05
11

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.

  • 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.2012-11-05