Question 2.34

4.

  1. For the graph below, write down a Hamiltonian circuit that starts at X3.
    image
  2. How many vertices are there in the Hamiltonian circuit you found in part (a)?
  3. How many edges are there in the Hamiltonian circuit you found in part (a)?
  4. What is the largest number of edges you can remove from the graph shown in part (a) that will still allow one to find a Hamiltonian circuit in the graph after the edges are removed?