2.1.2. Dirac's Theorem

Try these first

1. 1.

   What is a Hamiltonian circuit?

   Hint

   Think about paths that start and end at the same point.

2. 2.

   State Dirac's Theorem.

   Hint

   Focus on vertex degrees in relation to the number of vertices.

3. 3.

   What does Dirac's Theorem state?

   • The sum of the degrees of non-adjacent vertices is always less than n.
   • A connected graph is Hamiltonian if every vertex has degree at least n/2.
   • All Eulerian graphs are Hamiltonian.

   Hint

   Focus on the degree condition related to connected graphs.

4. 4.

   True or False: Ore's condition is more restrictive than Dirac's.

   • True
   • False

   Hint

   Consider the flexibility in vertex degree comparisons.

5. 5.

   Given a connected graph of 8 vertices where each vertex has a degree of 4, is the graph Hamiltonian? Explain with reference to Dirac's Theorem.

   Hint

   Check if the vertex degrees meet the necessary condition.

6. 6.

   Construct a graph with 6 vertices that satisfies Ore's condition yet lacks a Hamiltonian circuit. Demonstrate how.

   Hint

   Consider what non-adjacency and degree sums indicate toward connectivity.