Prove o Teorema (Bondy–Chvátal’1976): Um grafo simples é hamiltoniano se, e somente se, seu fecho hamiltoniano é hamiltoniano. 1. IDA(⇒): Denot...

Prove o Teorema (Bondy–Chvátal’1976): Um grafo simples é hamiltoniano se, e somente se, seu fecho hamiltoniano é hamiltoniano.

1. IDA(⇒): Denotaremos [G] como o fecho hamiltoniano de um grafo G. Primeiro observe que [G] possui o mesmo conjunto de vértices de G e seu conjunto de arestas é formado pelas arestas de G com, possivelmente, arestas adicionadas, ou seja, temos G ⊆ [G] com V (G) = V ([G]). Então se existe um ciclo hamiltoniano C em G, então C também será um ciclo hamiltoniano em [G].
2. VOLTA(⇐): Seja o fecho [G] constrúıdo tal que G = G1, G2, . . . , Gk = [G], onde todo Gi é o passo da construção que adiciona uma aresta entre um par de vértice x, y ∈ V tal que d(x) + d(y) ≥ |V (Gi−1)|. Precisamos mostrar apenas que se Gi é hamiltoniano, então Gi−1 é hamiltoniano. Para tal, basta observarmos o Teorema de Ore apresentado em sala (Grafos hamiltonianos – II). Observe que Gi−1 satisfaz as hipóteses do Teorema de Ore, então temos que se Gi é Hamiltoniano, então Gi−1 é hamiltoniano, pois existe u, v ∈ V tal que d(v) + d(u) ≥ n. Desta forma, podemos aplicar em Gi e Gi−1 para i = 2, . . . , k e o resultado segue.