# Does there exist a $10$-vertex graph with degrees $1, 1, 3, 3, 6, 6, 6, 7, 8, 9$?

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

-
Are we allowing multiple edges between two vertices? Are we allowing edges that begin and end on the same vertex? – Logan Stokols Nov 5 '12 at 5:14

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

-
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.

-
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