The parts of this exercise outline a proof of Ore’s theorem. Suppose that G is a simple graph with n vertices, n ≥ 3, and deg(x) + deg(y) ≥ n whenever x and y are nonadjacent vertices in G. Ore’s theorem states that under these conditions, G has a Hamilton circuit.
a) Show that if G does not have a Hamilton circuit, then there exists another graph H with the same vertices as G, which can be constructed by adding edges to G such that the addition of a single edge would produce a Hamilton circuit in H.
b) Show that there is a Hamilton path in H.
c) Let v1, v2, . . . , vn be a Hamilton path in H. Show that deg(v1) + deg(vn) ≥ n and that there are at most deg(v1) vertices not adjacent to vn (including vn itself).
d) Let S be the set of vertices preceding each vertex adjacent to v1 in the Hamilton path. Show that S contains deg(v1) vertices and vn S.
e) Show that S contains a vertex vk, which is adjacent to vn, implying that there are edges connecting v1 and vk+1 and vk and vn.
f) Show that part (e) implies that v1, v2, . . . , vk−1, vk, vn, vn−1, . . . , vk+1, v1 is a Hamilton circuit in G. Conclude from this contradiction that Ore’s theorem holds.