Redator: Jorge Alencar Data de Resolução: 06 - Março

Exercício 1.1.31: Prove que um grafo autocomplementar de n vértices existe se, e somente se, 4 divide n ou n − 1.

(⟹) Suponha que exista um grafo G autocomplementar com n vértices. Logo G ≃ Ḡ, onde Ḡ é o grafo complementar de G. Isso implica que |E(G)| = |E(Ḡ)|. Por definição de grafo complementar temos que a soma da quantidade de aresta do grafo G e de seu complementar é igual a quantidade de aresta do grafo completo com n vértices, logo

|E(G)| + |E(Ḡ)| = \frac{n(n − 1)}{2}
|E(G)| + |E(G)| = \frac{n(n − 1)}{2}
2|E(G)| = \frac{n(n − 1)}{2}
|E(G)| = \frac{n(n − 1)}{4}

Como |E(G)| é um número inteiro, então 4 divide n ou n − 1.

(⟸) Suponha que 4 divide n, isso implica que existe m tal que n = 4m. Dividimos o n vértices em 4 grupos de m vértices, e construímos 4 grafos G_{1} = K_{m},G_{2} = 0_{m},G_{3} = 0_{m} e G_{4} = K_{m}, onde 0_{m} é um grafo de m vértices e zero arestas. Criamos subgrafos K_{m,m} entre os pares de subgrafos (G_{1}, G_{2}),(G_{3}, G_{2}) e (G_{3}, G_{4}). Obtendo algo como na figura1 em anexo.

Se conjugarmos o grafo obtido temos o grafo da figura2, que é claramente isomorfo ao da figura1.

Suponha que 4 divide n − 1, isso implica que existe m tal que n = 4m + 1. Dividimos o n vértices em 4 grupos de m vértices e um grupo H com apenas 1 vértice, e construímos 4 grafos G_{1} = K_{m},G_{2} = 0_{m},G_{3} = 0_{m} e G_{4} = K_{m}, onde 0_{m} é um grafo de m vértices e zero arestas. Criamos subgrafos K_{m,m} entre os pares de subgrafos (G_{1}, G_{2}),(G_{1}, G_{4}) e (G_{3}, G_{4}),e subgrafos K_{1,m} entre os pares de subgrafos (G_{2}, H) e (G_{3}, H). Obtendo algo como na figura3 em anexo.

Se conjugarmos o grafo obtido temos o grafo da figura4, que é claramente isomorfo ao da figura3.

As figuras 4 e 5 representam graficamente o que esta acontecendo com m = 3 em ambos os casos.