9780023606922, Chapter 2 5, Problem 55E

Prévia do material em texto

Chapter 2.5, Problem 55E 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 Consider the following graph : I 2 3 4 5 6 The path (6,4,1,2,3,5,6) covers all the vertices of the graph only once, except the beginning and the ending vertex which is 6. From the definition, a Hamiltonian cycle happens in the graph Hence, the graph has a Hamiltonian cycle