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$?
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$?
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$?
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).
We can go ahead and stop because no vertex can have degree of $-1$. By the theorem, your original sequence cannot be realized either.