I'm taking a class in Discrete Mathematics, and one of the problems in my homework asks for a Simple Graph with 5 vertices of degrees 2, 3, 3, 3, and 5. How can I have more than 4 edges? I'm really confused, maybe I don't really understand what a "Simple Graph" means.

  • $\begingroup$ What do you think the definition of "simple graph" is? $\endgroup$ – Randall Dec 3 '18 at 2:33
  • $\begingroup$ Has no loops, no multi-edges. $\endgroup$ – Ayaan Siddiqui Dec 3 '18 at 2:34
  • $\begingroup$ Have you considered the fact that they might have intended for you to state that such a graph cannot exist? $\endgroup$ – Boshu Dec 3 '18 at 2:36
  • $\begingroup$ Since there are $5$ vertices, no vertex can have degree more than $4$. $\endgroup$ – the_fox Dec 3 '18 at 2:36
  • $\begingroup$ Looks like professor made a typo then $\endgroup$ – Ayaan Siddiqui Dec 3 '18 at 2:36

Since you only have 5 vertices, it is not possible in a simple graph to have a maximum degree of more than $5-1=4$. Hence, such a simple graph as required does not exist.


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.