9780023606922, Chapter 2 5, Problem 57E

Prévia do material em texto

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