Prove que se dois grafos são isomorfos, então possuem a mesma seqüência de graus.

Para provar que se dois grafos são isomorfos, então possuem a mesma sequência de graus, podemos utilizar o Teorema do Handshake, que afirma que a soma dos graus de um grafo é sempre par. Suponha que G e H sejam dois grafos isomorfos. Seja V(G) o conjunto de vértices de G e V(H) o conjunto de vértices de H. Como G e H são isomorfos, existe uma bijeção f: V(G) → V(H) que preserva as adjacências. Seja d(v) o grau do vértice v em G. Então, a soma dos graus de G é d(G) = Σv∈V(G) d(v). Como G e H são isomorfos, podemos escrever d(G) = d(H), onde d(H) é a soma dos graus de H. Agora, vamos mostrar que a sequência de graus de G e H é a mesma. Seja n o número de vértices de G e H. Considere a sequência de graus de G: d1, d2, ..., dn. Como G e H são isomorfos, podemos escrever a sequência de graus de H como d(f(1)), d(f(2)), ..., d(f(n)), onde f é a bijeção que preserva as adjacências. Observe que a soma dos graus de G é igual à soma dos graus de H, ou seja, d1 + d2 + ... + dn = d(f(1)) + d(f(2)) + ... + d(f(n)). Como f é uma bijeção, podemos reordenar os termos da sequência de graus de H para obter d1 + d2 + ... + dn = d(1) + d(2) + ... + d(n). Portanto, a sequência de graus de G e H é a mesma. Assim, podemos concluir que se dois grafos são isomorfos, então possuem a mesma sequência de graus.