The Path of Euler and Hamilton
Even though the origin of the traveling salesman problem was initially associated more with salesmen, preachers, and lawyers, it gained mainstream recognition after mathematicians like Euler and Hamilton tackled the challenge.
Euler presented his paper on the Konigsberg problem to the Academy of Science in St. Petersburg on August 26, 1735. In this paper, he posed the challenge of crossing all the bridges only once on a single walk.
The Konigsberg problem involved redrawing the city’s map with lands (Red — B, Orange — A, Blue — C & White — D) as vertices and bridges (a, b, c, d, e, f & g) as edges.
One of the ways to cross the bridges by revisiting some places and skipping a few bridges can be represented as BaAcCgDeAb. In this solution, except for the starting (B) and end (D) points, all other places had an even number of visited paths (edges). If we close the start and end points, then all vertices have an even number of edges.
As each vertex (land) had an odd number of edges in the Konigsberg problem, it was concluded by Euler that it was not possible to cross all the edges (bridges) only once on a single walk. This discovery marked the birth of graph theory and became known as the Euler Path problem.
Sir William Rowan Hamilton later designed a game in which the player had to cross all vertices only once on a single walk. While it seemed difficult for this legendary mathematician, children could solve it visually with ease. Perhaps Hamilton used algebraic methods in his approach. The game was later improved by James Dalgety and commercially released as Worried Woodwarm. This concept falls under the Hamiltonian Circuit category in graph theory.
To rephrase the above, an Euler path involves visiting all the edges only once, while a Hamiltonian circuit involves visiting all the vertices only once.
Identifying a problem that belongs to the Euler path category is easy, but deciding whether a problem falls under the Hamiltonian circuit category is challenging. In fact, it falls into the NP problem category. Many great mathematicians proposed conjectures to guarantee the existence of Hamiltonian circuits in problems, only to have them disproven.
Alfred Kemp posted a solution to the four-color problem in 1880, stating that any map can be colored with four colors at most without two neighboring zones sharing the same color. While seeking an alternative proof, P. G. Tait conjectured that certain types of graphs always have a Hamiltonian circuit.
The image on the left shows a graph with an Hamiltonian circuit connecting all the vertices. The inner area within the red boundary edge can be further connected with edges that are not part of the boundary edge. Two alternative colors (yellow and orange) are sufficient to color them. Similarly, the outer area can be colored with blue and dark blue.
This apparently led Tait to conjecture that any three-edge connected map can always have a Hamiltonian circuit. However, this conjecture was later disproven. Thus, it is not easy to identify Hamiltonian circuit problems.
