Mostre que tanto
quanto
se tornam planares após remoçäo de um arco qualquer.
Passo 1
O enunciado está em teoria de grafos: precisamos mostrar que, ao remover qualquer aresta de
ou de
, o grafo que sobra é planar. A estratégia usa o seguinte fato (lema de inserção de vértice):
se um grafo é planar e os vizinhos de
aparecem todos na fronteira de uma mesma face de uma planarização de
, então podemos inserir
dentro dessa face e ligar
aos seus vizinhos sem cruzar arestas, obtendo uma planarização de
.
se um grafo
Passo 2
Considere
e seja
qualquer aresta. No grafo
, os vértices
e
têm grau 3. Remova
; então
que é planar (é só desenhar um tetraedro). Num desenho de
, os três vizinhos de
, digamos
, fazem exatamente um ciclo triangular e delimitam uma face
. Agora, para reconstruir
, colocamos
dentro de
e traçamos arestas curvas de
a
,
e
totalmente contidas em
. Como nada sai de
, não há cruzamentos. Logo
é planar.
Passo 3
Considere
com partições
e
e seja
qualquer aresta. No grafo
, o vértice
agora tem grau 2 (está ligado apenas a
). Remova
; então
que é planar (é simplesmente o bi–grafo com 2 vértices de um lado e 3 do outro). Em qualquer planarização de
(que é 2-conexo), existe uma face
cuja fronteira contém os vizinhos de
, isto é,
e
. Basta inserir
dentro de
e ligar
a
por arcos dentro de
. Assim não surgem cruzamentos e
é planar.
Resposta
Mostramos que, para qualquer aresta
, tanto
quanto
admitem um desenho sem cruzamentos, logo são grafos planos.