The parts ofthis exercise outline a proof of Ore's

Chapter 9, Problem 9.5.65

(choose chapter or problem)

The parts ofthis 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 V I , V2 , ... , Vn be a Hamilton path in H. Show that deg(vI) + deg(vn) ::: n and that there are at most deg( V I) vertices not adjacentto Vn (including Vn itself). d) Let S be the set of vertices preceding each vertex adjacent to VI in the Hamilton path. Show that S contains deg(vI) vertices and Vn !if- S. e) Show that S contains a vertex Vk , which is adjacent to Vn , implying that there are edges connecting VI and Vk+1 and Vk and Vn . t) Show that part (e) implies that V I , V2 , , Vk- I, Vb Vn , Vn- I, .. , Vk+ I, VI is a Hamilton circuit in G. Conclude from this contradiction that Ore's Theorem holds.