Question

What is the difference between a Eulerian Path and Circuit? What is the difference between a Hamiltonian Path and Circuit? Is the image below Eulerian or Hamiltonian, Path or Circuit? How did you determine your answer?

Answer 1

Euler paths and circuits :

• An Euler path is a path that uses every edge of a graph exactly once.
• An Euler circuit is a circuit that uses every edge of a graph exactly once.
• An Euler path starts and ends at different vertices.
• An Euler circuit starts and ends at the same vertex.

Hamiltonian paths and circuits :

Hamilonian Path – A simple path in a graph that passes through every vertex exactly once is called a Hamiltonian path.

Hamilonian Circuit – A simple circuit in a graph that passes through every vertex exactly once is called a Hamiltonian circuit.

Unlike Euler paths and circuits, there is no simple necessary and sufficient criteria to determine if there are any Hamiltonian paths or circuits in a graph. But there are certain criteria which rule out the existence of a Hamiltonian circuit in a graph, such as- if there is a vertex of degree one in a graph then it is impossible for it to have a Hamiltonian circuit.