Caracterização de sequências gráficas

Resumo

Seja G um grafo simples de ordem n. A sequência de graus de G é uma n-upla cujas coordenadas, dadas em ordem não crescente, correspondem aos graus dos vértices de G. Uma sequência de graus, em geral, não identifica unicamente um grafo. A Figura 1 exibe as árvores T1 e T2 com a mesma sequência de graus (3, 2, 2, 2, 2, 1, 1, 1).