Ian Short - Hamilton cycles

Hamilton cycles

22 March 2010

Introduction

Recall that an Euler trail is a walk through a graph that covers each edge once and only once. A Hamilton path is a walk through a graph that covers each vertex once and only once. In other words, a Hamilton path is a path that contains every vertex. A Hamilton cycle is a cycle that contains every vertex of the graph. Below are the nets of the five Platonic solids. Can you identify which net corresponds to which Platonic solid? Which of the nets contains a Hamilton cycle?

Investigation 1: complete graphs

Complete graphs contain Hamilton cycles. You can experiment with Graph Constructor to see that this is true; use the 'select graph' button, and choose 'complete'. How many Hamilton cycles does a complete graph with n vertices have?

Investigation 2: Dirac's Theorem

Dirac's Theorem applies only to graphs which do not contain multiple edges between vertices, and which do not have edges connecting vertices to themselves. All our graphs have been declared to be of this type. Some textbooks on graph theory describe such graphs as simple graphs. Loosely speaking, Dirac's Theorem says that if your graph has enough edges, then it admits a Hamilton cycle.

Dirac's Theorem. A graph with n vertices (where n>2) has a Hamilton cycle if each vertex has degree at least n/2.

Prove that each complete graph has a Hamilton cycle by using Dirac's Theorem. Can you find graphs with Hamilton cycles for which the degree of each vertex is not at least n/2?

Investigation 3: Cheese problem