9780023606922, Chapter 2 5, Problem 54E

Prévia do material em texto

Chapter 2.5, Problem 54E Step-by-step solution Step 1 of 1 Finding the Hamiltonian Cycle in a Graph Hamiltonian Cycle: If a cycle of a graph G contains every vertex in a graph G only once and the beginning and ending vertices are the same then the cycle is called as Hamiltonian cycle of the graph G. Consider the following graph: 1 2 e₁ e₂ e₃ e₄ e₅ 3 e₆ 4 e₇ 5 The path (1,2,3,5,4,1) covers all the vertices of the graph only once, except the beginning and the ending vertex which is 1. From the definition, a Hamiltonian cycle happens in the graph. Hence, the graph has a Hamiltonian cycle