Let G(V,E) be a simple graph of order n and δ the minimum degree of vertices. Suppose that the degree sum of any pair of nonadjacent vertices is at least n and F ⊂ E with |F| ≤ ⌊δ−2⌋/2. Let G − F be the graph obtained from G by deleting the edges in F . Prove that (1) G − F is connected and (2) G − F is Hamiltonian.
Actually, it was a problem in S.T.Yau contest. I'm trying to solve this...