4 Determine whether each of the following graphs has a Hamil

4. Determine whether each of the following graphs has a Hamiltonian circuit. If it does have an Hamiltonian circuit, find such a circuit. If it does not have an Hamiltonian circuit, explain why you can he 100% sure that it does not.

Solution

Both these graphs does not contain a hamiltonian circuit.

First Graph:

In the first graph, vertices h and g both connect two closed graphs. Hence, we can use either of these two vertices for one graph only. If we would want to use make a closed hamiltonian circuit, we will have to pass through h and g twice, which by definition of Hamiltonion circuit is not allowed. Hence no Hamiltonian Circuit exists for this graph.

Second Graph:

In second graph, vertex i connects two closed graphs. Hence, in order to cover all the vertices in a closed path, we will have to pass through vertex \'i\' twice, which is now allowed, hence the Hamiltonian Circuit is not possible for this graph either.