9780023606922, Chapter 2 5, Problem 58E

Prévia do material em texto

Chapter 2.5, Problem 58E 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 K5 : 2 1 3 5 4 The path (1,2,3,4,5,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 occurs in the graph Hence, the graph K5 has a Hamiltonian cycle