Mostre que tanto K_{5} quanto K_{3,3} 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 K_5 ou de K_{3,3}, o grafo que sobra é planar. A estratégia usa o seguinte fato (lema de inserção de vértice):
se um grafo G - v é planar e os vizinhos de v aparecem todos na fronteira de uma mesma face de uma planarização de G - v, então podemos inserir v dentro dessa face e ligar v aos seus vizinhos sem cruzar arestas, obtendo uma planarização de G.

Passo 2

Considere K_5 e seja e=uv qualquer aresta. No grafo G = K_5 - e, os vértices u e v têm grau 3. Remova v; então
G - v = K_4,
que é planar (é só desenhar um tetraedro). Num desenho de K_4, os três vizinhos de v, digamos \{a,b,c\}, fazem exatamente um ciclo triangular e delimitam uma face F. Agora, para reconstruir G, colocamos v dentro de F e traçamos arestas curvas de v a a, b e c totalmente contidas em F. Como nada sai de F, não há cruzamentos. Logo K_5 - e é planar.

Passo 3

Considere K_{3,3} com partições X=\{x,u_1,u_2\} e Y=\{y,v_1,v_2\} e seja e=xy qualquer aresta. No grafo H = K_{3,3}-e, o vértice x agora tem grau 2 (está ligado apenas a v_1,v_2). Remova x; então
H - x = K_{2,3},
que é planar (é simplesmente o bi–grafo com 2 vértices de um lado e 3 do outro). Em qualquer planarização de K_{2,3} (que é 2-conexo), existe uma face F' cuja fronteira contém os vizinhos de x, isto é, v_1 e v_2. Basta inserir x dentro de F' e ligar x a v_1,v_2 por arcos dentro de F'. Assim não surgem cruzamentos e K_{3,3}-e é planar.

Resposta

Mostramos que, para qualquer aresta e, tanto K_5-e quanto K_{3,3}-e admitem um desenho sem cruzamentos, logo são grafos planos.

Exercícios de Livros Relacionados