HAMILTONIAN PATH
This concept is named after Sir William Rowan Hamilton, an Irish mathematician, astronomer, and physicist who worked on graph theory in the 19th century.
A Hamiltonian path is a path in a graph that visits each vertex exactly once. It doesn't necessarily visit every edge in the graph, but it must cover all vertices without repetition. So, it is a sequence of vertices
where each vertex is connected to the next by an edge, and no vertex is visited more than once. Such a path can be thought of as a "tour" of the graph, where you visit every location exactly once.
Not all graphs have Hamiltonian paths, and determining whether a given graph has one can be a challenging computational problem.
The “Icosian” game was also invented by Hamilton. Note that the board is the flattening of the edges and vertices of a regular dodecahedron (a polyhedron with twelve faces, all pentagonal).
On this board, we can propose several challenges, ranging from easy to impossible!
One of the first challenges is finding a path passing through each point exactly once. This type of path in graphs became known as a Hamiltonian path. The path is called a circuit if it returns to the starting point. On Eulerian paths (see Königsberg Bridges), one passes exactly once on each edge.
Image: Alisson Ricardo.
As for the next ones, find a Hamiltonian path: with the numbered pins, create a path that passes only once through each vertex. Is it possible to create a Hamiltonian cycle? That is, where the last vertex of the path is adjacent to the first?
Try to do the same things on both boards
Do you notice any essential difference between them?
Now, block one of the vertices as if it no longer exists in the graph. Can you still find a Hamiltonian path? What about a cycle? How does this change if you block a different vertex instead?
You can also block two or more vertices.
By doing this, you may encounter situations with no solution at all!
