The tutor proves the existence of a Hamilton cycle under certain conditions.

A Hamilton cycle, named for the Irish mathematician Sir William Rowan Hamilton, is a path that visits each vertex of a graph exactly once before returning to the start point. On page 586 of Grimaldi, the reader is asked to prove the following:

A graph with n ≥ 3 vertices, with deg ≥ n/2 for each one, has a Hamilton cycle.

Proof:

We will prove by induction. For the case of 3 vertices, each with degree 2, there is obviously a Hamilton cycle:

Let’s now assume a graph of n vertices with a Hamilton cycle. If we add another vertex, |V| = n + 1. The the new vertex itself has deg ≥ (n+1)/2, which means it joins to more than half of the n orginal points. Perhaps only because they form a cycle, two of those points must be adjacent. Let’s imagine those points are P_q and P_r. Then the new point can be included in the cycle between P_q and P_r. So, the new graph with n + 1 vertices also has a Hamilton cycle.

I’ll be discussing more graph theory in future posts:)

Source:

Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. Don Mills: Addison-
  Wesley, 1994.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.