2
$\begingroup$

Does the following graph exist?

A graph with 100 vertices, in which 10 vertices have degree 90 each and each of the remaining 90 vertices has degree 8.

If it exists, is there any example? If it does not exist, how to prove it?

$\endgroup$
  • $\begingroup$ Havel-Hakimi algorithm answers questions like this once and for all, but in this particular case you may indeed use simpler considerations. $\endgroup$ – Ivan Neretin Oct 16 '16 at 8:02
3
$\begingroup$

Hint: there are at least $810$ edges joining the first $10$ vertices to the other $90$. But then ...

$\endgroup$

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.