9780023606922, Chapter 2, Problem 29E

Prévia do material em texto

Chapter 2, Problem 29E Step-by-step solution Step of 5 Hamiltonian cycle Consider the following graph with n> m vertices as shown below, and we need to find out if it contains a Hamiltonian m vertices n vertices Step of 5 we see if not both m and n are we can find a Hamiltonian cycle easily by traversing through each column one by one as shown: When m vertices n vertices Step of 5 When even: m vertices . n vertices Step of 5 We see that, which side is even, we can run the edges along rows or columns as shown in the above But when both and m are odd. we cannot decide at least find the Hamiltonian cycle this way, if at all exists Step of 5 We know attempt to prove that Hamiltonian cycle does not exist if both and m are Since if we represent the cycle with directed edges, for any cycle in the graph, the number of arrows towards right will be equal to the number of edges towards the left, so that the sum of the number of arrows towards the right and the number of arrows towards the left will be even, on similar analogy, the number of arrows upwards will be equal to the number of edges so that the sum of the number of arrows downwards and the number of arrows upwards will be This means that the sum of all the edges (or arrows) will be even, but for a simple cycle, the number of edges is same as the number of vertices. Also, we know that for this graph, the number of vertices is mn, which odd, therefore, no simple cycle can exist consisting of all the vertices Therefore, the graph will contain a Hamiltonian cycle at least one of m and n. is