Question 39
$G$ and $G'$ are graphs (without loops and multiple edges) on the same set of 100 vertices. Two vertices are connected by an edge in the graph $G'$ iff the sum of their degrees in the graph $G$ is at least 100. The graph $G'$ has a Hamiltonian cycle (i.e. a cycle of length 100 that passes through all the vertices). Prove that $G$ also has a Hamiltonian cycle.