Seja X um conjunto finito, e seja P(X) o conjunto das partes de X. Seja G o grafo cujos vértices representam os elementos de P(X), em que A e B estão conectados por uma aresta se A cap B=emptyset. Similarmente, seja H um grafo com um vértice para cada elemento de P(X), mas onde A e B compartilham uma aresta se A cup B=X. Prove que G é isomorfo a H.

Passo 1

O enunciado define dois grafos sobre o mesmo conjunto de vértices, que é P(X). No grafo G, dois vértices A e B estão ligados se e somente se ,Acap B=emptyset. No grafo H, eles estão ligados se e somente se ,Acup B=X. O objetivo é mostrar que existe um isomorfismo de grafos entre G e H.

Passo 2

Definimos a aplicação
fcolon P(X)longrightarrow P(X), f(A)=Xsetminus A
Como X é finito, fica claro que f é bijetora (é involutória, pois f(f(A))=A). Logo, f estabelece uma correspondência biunívoca entre os vértices de G e de H.

Passo 3

Resta verificar que f preserva arestas. Observe que, para quaisquer A,Bsubseteq X, vale
Acap B=emptyset Long<=ftrightarrow (Xsetminus A)cup (Xsetminus B) = Xsetminus (Acap B) = X
Portanto
(A) e (B) adjacentes em (G) Long<=ftrightarrow Acap B=emptyset Long<=ftrightarrow f(A)cup f(B)=X Long<=ftrightarrow (f(A)) e (f(B)) adjacentes em (H)
Isso mostra que f leva arestas de G em arestas de H e vice-versa.

Resposta

A bijeção f(A)=Xsetminus A é um isomorfismo de G em H, logo Gcong H.

Exercícios de Livros Relacionados