Exercise · ZW-HAMILTONIAN-CYCLE-006 · ★★☆ Intermediate
The bowtie is two triangles sharing one vertex (5 vertices). Which is true?
Choose one option.
Show answer
- A. It has an Eulerian but not a Hamiltonian cycle
Explanation
The degrees are \(4,2,2,2,2\), all even, and it is connected: it is Eulerian. But the shared vertex would have to be visited twice to cover both triangles, so it is not Hamiltonian.
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-007 Which condition prevents a graph from having a Hamiltonian cycle?
- ZW-HAMILTONIAN-CYCLE-008 In the cube Q_3 (vertices: 3-bit strings; edges: strings differing in one bit), which list is a Ham…
- ZW-HAMILTONIAN-CYCLE-009 A bipartite graph has parts of 4 and 5 vertices. Can it have a Hamiltonian cycle?