9780023606922, Chapter 2, Problem 30E

Prévia do material em texto

Chapter 2, Problem 30E Step-by-step solution Step 1 of 2 Hamiltonian cycle The following graph with nx as shown below and we need to find out if it contains a Hamiltonian cycle. m vertices n vertices Step 2 of 2 We know that for any graph to contain an Euler's cycle, every vertex should have even number of edges incident to it. For if there are one or more vertices with odd number of vertices incident, we cannot create a cycle using all those edges, and since at least some edges will have to be missed, an Euler's cycle can't be obtained for the graph. With the given graph, we see that all the vertices in either first or last row; or either first or last column; but not both, have exactly three edges, so the graph can't contain an Euler's cycle, except for n = m = 2.