2.1. Hamiltonian Circuit

Try these first

1. 1.

   Define Hamiltonian circuit in your own words.

   Hint

   Think of a tour where you return to the start.

2. 2.

   What is the key difference between Hamiltonian and Eulerian circuits?

   Hint

   Consider what each path emphasizes.

3. 3.

   What is a Hamiltonian Circuit?

   • Visits every edge
   • Visits every vertex exactly once
   • Starts and ends at different points

   Hint

   Compare with Euler circuits.

4. 4.

   True or False: Ore’s theorem can guarantee a Hamiltonian graph for all configurations.

   • True
   • False

   Hint

   Consider if other conditions exist.

5. 5.

   Create a graph of 6 vertices that fails both Dirac's and Ore's conditions but is still Hamiltonian.

   Hint

   Think of how to strategically place vertices for limited connections.

6. 6.

   Using Ore's theorem, illustrate how to modify a graph to ensure it meets Hamiltonian conditions.

   Hint

   Identify pairs and keep track of their degree counts.