Num grafo de ordem qualquer vértice pode ligar no máximo a todos os outros vértices pelo que o seu grau é:
Vamos assumir por absurdo que não há 2 vértices com o mesmo grau (todos os vértices têm grau diferente). A sequência de graus do grafo seria:
éMas a sequência em questão não é gráfica pois se o 1º vértice tem grau , está ligado a todos os outros, logo o último vértice não pode ter grau (estar isolado).