The parts of this exercise outline a proof of Ore’s

Chapter , Problem 65E

(choose chapter or problem)

Problem 65E

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. [Hint: Add as many edges as possible at each successive vertex of G without producing a Hamilton circuit.]

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.