Seja
um conjunto finito, e seja
o conjunto das partes de
. Seja
o grafo cujos vértices representam os elementos de
, em que
e
estão conectados por uma aresta se
. Similarmente, seja
um grafo com um vértice para cada elemento de
, mas onde
e
compartilham uma aresta se
. Prove que
é isomorfo a
.
Passo 1
O enunciado define dois grafos sobre o mesmo conjunto de vértices, que é
. No grafo
, dois vértices
e
estão ligados se e somente se
. No grafo
, eles estão ligados se e somente se
. O objetivo é mostrar que existe um isomorfismo de grafos entre
e
.
Passo 2
Definimos a aplicação
Como
é finito, fica claro que
é bijetora (é involutória, pois
). Logo,
estabelece uma correspondência biunívoca entre os vértices de
e de
.
Passo 3
Resta verificar que
preserva arestas. Observe que, para quaisquer
, vale
Portanto
Isso mostra que
leva arestas de
em arestas de
e vice-versa.
Resposta
A bijeção
é um isomorfismo de
em
, logo
.