Does there exist a simple graph with the degree sequence

3.6k Views Asked by At

Does there exist a simple graph with 7 vertices and the degree sequence {0,2,2,2,3,5,6}?

I know that the Handshaking Lemma says that the sum of the degrees is twice the number of edges. In this case the number of edges is 20, which means that the graph must exist. However, the part I'm iffy about is can a simple graph have a vertex with degree zero?

2

There are 2 best solutions below

0
On

Hint: Vertex number $7$ has degree $6$, which means it must be joined to every other vertex. But...

2
On

Hint If you have a simple graph with $7$ vertices, and one has degree $6$, what does this mean?