2.1.5. Critical Pair of Vertices and Conclusion

Try these first

1. 1.

   Define a Hamiltonian circuit.

   Hint

   Think about the properties of simple circuits.

2. 2.

   What defines a Hamiltonian path?

   Hint

   Focus on the difference from circuits.

3. 3.

   Which of the following defines a Hamiltonian circuit?

   • Visits every vertex at least once
   • Visits every edge at least once
   • Visits every vertex exactly once and returns to the starting vertex

   Hint

   Focus on the goal of the circuit.

4. 4.

   True or False: A Hamiltonian graph must always satisfy Dirac's theorem.

   • True
   • False

   Hint

   Consider examples that challenge the theorem.

5. 5.

   Given a complete graph with n vertices, prove it is Hamiltonian using Dirac's theorem.

   Hint

   Consider the definition of complete graphs.

6. 6.

   Construct examples of graphs that do not satisfy Ore's condition but are still Hamiltonian and explain your findings.

   Hint

   Think about different structures that still connect all vertices.