Let the cycle you had be v₁, v₂, ..., v_n and you have deleted edge between v_n and v₁. Now for each vertex put a candy on it if it's adjacent to v₁ in the current graph. Also put a candy on vertex v_i if v_i - 1 is adjacent to v_n. Because n ≤ deg(v₁) + deg(v_n) and there are n - 1 vertices capable of receiving candy you can prove by Pigeon Hole Principle (although its obvious) that there exists a vertex which has received two candies. Suppose v_i has received 2 candies. This means that v₁ is adjacent to v_i and v_i - 1 is adjacent to v_n. So you can build a new Hamiltonian cycle like this: v₁, v₂, ..., v_i - 1, v_n, v_n - 1, ..., v_i, v₁.