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...

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
v
₁,
v
₂
, . . . , v_n
be a Hamilton path in
H. Show that deg(v
₁
)
+ deg(v_n)
≥
n
and that there are at most deg(v
₁
)
vertices not adjacent to
v_n
(including
vn
itself).

d) Let
S
be the set of vertices preceding each vertex adjacent to
v
₁
in the Hamilton path. Show that
S
contains deg(v
₁
)
vertices and
v_n
S.

e) Show that
S
contains a vertex
v_k
, which is adjacent to
v_n
, implying that there are edges connecting
v
₁
and
v<sub>k

+
1</sub>
and
v_k
and
v_n
.

f) Show that part (e) implies that
v
₁,
v
₂
, . . . , v<sub>k

−
1</sub>
, v_k, v_n, v<sub>n

−
1</sub>
, . . . , v<sub>k

+
1</sub>
, v1 is a Hamilton circuit in
G. Conclude from this contradiction that Ore’s theorem holds.