2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ In a simple graph, you can't have a degree 6 vertex when my only options for connecting that vertex are 5 other vertices. So the simple graph for the sequence doesn't exist? $\endgroup$ – Amous Mar 30 '14 at 4:47
  • $\begingroup$ @user132909 Yes. $\endgroup$ – N. S. Mar 30 '14 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.