The planarity algorithm and Hamiltonian cycles Quiz

1. A graph has 7 vertices and 6 edges and is connected. Does it have a Hamiltonian cycle?

• A. Yes, always
• B. Only if it is Eulerian
• C. Not enough information
• D. No

2. In the planarity algorithm for a cycle $ABCDEF$, which chord conflicts with $AC$?

• A. $BE$
• B. $AD$
• C. $CE$
• D. $AE$

3. Two conflicting chords are drawn...

• A. both inside the cycle
• B. both outside the cycle
• C. on opposite sides of the cycle
• D. along the cycle

4. The chord $XY$ conflicts with one chord inside and one chord outside. What can you conclude?

• A. The graph is non-planar
• B. The graph is planar
• C. The graph is Eulerian
• D. The cycle is not Hamiltonian

5. Which statement is correct?

• A. A Hamiltonian cycle uses every edge once
• B. A Hamiltonian cycle visits every vertex once
• C. A Hamiltonian cycle needs all degrees even
• D. Every Hamiltonian graph is planar