9780023606922, Chapter 2 5, Problem 63E

Prévia do material em texto

Chapter 2.5, Problem 63E Step-by-step solution Step 1 of 1 Hamiltonian Cycle in a Graph Hamiltonian Cycle: If a cycle of a graph G contains every vertex in a graph only once and the beginning and ending vertices are the same then the cycle is called as Hamiltonian cycle of the graph G. Dodecahedron: It is a polyhedron with 12 sides and these sides are pentagons. Consider the following graph 1 2 3 10, 18 12 13 4 90 19 16 14 15 05 8 20 6 There are two pentagons (11,12,19,20,16,11) and (15,14,13,18,17,15) connected with a decagon (1,2,3,4,5,6,7,8,9,10) in the graph dodecahedron. From the graph, the path covers all the vertices of the graph only once, except the beginning and the ending vertex which is 1. So, from the definition, a Hamiltonian cycle happens in the graph. Hence, a Hamiltonian cycle in the graph is