A noncomplete graph $H$ of order $5$ or more with the property that $deg (u) ≠ deg (v)$ for every pair $u, v$ of nonadjacent vertices of $H$.

Question

I'm working in the following graph theory excercise:

Give an example or explain why no such example exists of a noncomplete graph $H$ of order $5$ or more with the property that $deg (u) ≠ deg (v)$ for every pair $u, v$ of nonadjacent vertices of $H$.

I've reached the conclusion that is impossible that this graph exists because it can not be generated edges infinitely, is there a formalization that could help me to show it? Thanks in advance for any hint or help.

Answer 1

Does $$ H = ([5], \{(1,2),(2,3),(2,4),(3,4),(3,5),(4,5)\}). $$ satisfy your requirements?

I found it by considering the complement, which has the property that every pair of adjacent vertices has distinct degrees.