Hamilton Circuit Problem:-

3 min readSep 4, 2019

Definition: A Hamiltonian cycle is a cycle that contains all vertices in a graph . If a graph has a Hamiltonian cycle, then the graph is said to be Hamiltonian.

A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once . A graph possessing a Hamiltonian cycle is said to be a Hamiltonian graph.

The Hamiltonian cycle problem is a special case of the travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer).

Example:-

Solution: Firstly, we start our search with vertex 'a.' this vertex 'a' becomes the root of our implicit tree.

Next, we choose vertex 'b' adjacent to 'a' as it comes first in lexicographical order (b, c, d).

Next, we select 'c' adjacent to 'b.'

Next, we select 'd' adjacent to 'c.'

Next, we select 'e' adjacent to 'd.'

Next, we select vertex 'f' adjacent to 'e.' The vertex adjacent to 'f' is d and e, but they have already visited. Thus, we get the dead end, and we backtrack one step and remove the vertex 'f' from partial solution.

From backtracking, the vertex adjacent to 'e' is b, c, d, and f from which vertex 'f' has already been checked, and b, c, d have already visited. So, again we backtrack one step. Now, the vertex adjacent to d are e, f from which e has already been checked, and adjacent of 'f' are d and e. If 'e' vertex, revisited them we get a dead state. So again we backtrack one step.

Now, adjacent to c is 'e' and adjacent to 'e' is 'f' and adjacent to 'f' is 'd' and adjacent to 'd' is 'a.' Here, we get the Hamiltonian Cycle as all the vertex other than the start vertex 'a' is visited only once. (a - b - c - e - f -d - a).