Exercise · ZW-HAMILTONIAN-CYCLE-008 · ★★☆ Intermediate
In the cube \(Q_3\) (vertices: 3-bit strings; edges: strings differing in one bit), which list is a Hamiltonian cycle?
Choose one option.
Show answer
- D. 000, 001, 011, 010, 110, 111, 101, 100
Explanation
Each term must differ from the previous in one bit, with no repeats, and the last from the first. Only the list 000, 001, 011, 010, 110, 111, 101, 100 (a Gray code) does; the others have two-bit jumps or repeat a vertex.
Review the concept: Hamiltonian cycle
A Hamiltonian cycle of a graph \(G\) with \(n\ge 3\) vertices is a cycle that visits every vertex of \(G\) exactly once.
\[\deg(v)\ge \tfrac n2\ \forall v\ \Longrightarrow\ \text{Hamiltonian cycle exists}\]
More practice problems: hamiltonian cycle
- ZW-HAMILTONIAN-CYCLE-001 How many distinct Hamiltonian cycles does K_5 have, not counting the starting vertex or direction?
- ZW-HAMILTONIAN-CYCLE-002 Which of these graphs has a Hamiltonian cycle?
- ZW-HAMILTONIAN-CYCLE-003 Which of these complete bipartite graphs has a Hamiltonian cycle?
- ZW-HAMILTONIAN-CYCLE-004 A simple graph has 8 vertices and each has degree at least 4. What can be guaranteed?
- ZW-HAMILTONIAN-CYCLE-005 A Hamiltonian cycle of a graph with 9 vertices uses how many edges?
- ZW-HAMILTONIAN-CYCLE-006 The bowtie is two triangles sharing one vertex (5 vertices). Which is true?
- ZW-HAMILTONIAN-CYCLE-007 Which condition prevents a graph from having a Hamiltonian cycle?
- ZW-HAMILTONIAN-CYCLE-009 A bipartite graph has parts of 4 and 5 vertices. Can it have a Hamiltonian cycle?