Removendo ciclos em grafos

Manoel Lemos (UFPE)

Para um grafo G, o mínimo dos graus dos seus vértices é denotado por

δ(G) = min{d(v) : v ∈ V (G)}.

Dirac foi o primeiro a impor uma condição em δ(G) para garantir a existência de ciclos longos em grafos simples, mostrando os seguintes resultados: (a) G tem ciclo de comprimento pelo menos k + 1 quando δ(G) ≥ k + 1; (b) no caso em que G for 2-conexo, existe ciclo com pelo menos 2k arestas; (c) quando δ(G) ≥ |V (G)|/2, então G é hamiltoniano.

Já Mader estava interessado em garantir a existência de um ciclo em um grafo simples n-conexo cuja remoção de suas arestas mantivesse o grafo n-conexo. Conseguiu mostrar isto no caso em que δ(G) ≥ n + 2. Este teorema responde uma questão levantada por Hobbs, no caso em que o grafo é simples: “quando δ(G) ≥ 4 e G é 2-conexo, então G possui um ciclo cuja remoção o deixa 2conexo?”

Infelizmente esta questão não é verdadeira, como demonstrou Robertson. Jackson generalzou conjuntamente os resultados de Dirac e Mader, demon-

strando que todo grafo simples 2-conexo tal que δ(G) ≥ k possui um ciclo C com comprimento pelo menos k − 1 tal que G\E(C) é 2-conexo.

Iremos discutir generalizações do teorema de Jackson nesta mini-palestra.