# Does this 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.

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?

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

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