**@ dadoctah** …

You certainly put a lot of thought into this puzzler. Yes, the salesman must either start or finish in Maine if he is to visit each state once and only once. And New York state is unique in that it forms a barrier between the New England states and the remaining states — once past NY, going in either direction, the salesman can never return to the section he just left, be it New England or the lower states.

Some interesting solutions to 48-state problems from the Computer Sciences department at Carnegie-Mellon are given below:

Interesting Map Problems — CS@CMU

Hamitonian circuits/paths are similar mathematically to map-coloring problems, so that is why the two topics are discussed together in the above paper.

Hamiltonian circuits/paths (it is a *circuit* if the salesman returns to his starting point; it is a *path* if he does not) are extremely difficult to find, or even to show that one exists in a given problem. There is no algorithm that leads directly to a solution, or even one that tells if a solution exists. There are ad hoc heuristic approaches for some problems, however.

Hamitonian circuits/paths and map-coloring form a branch of mathematics called Graph Theory. The theory has numerous applications in the hard sciences, electrical engineering (designing complex circuit boards, for example), the biological sciences, and businesses (delivery truck routing comes to mind).

A brief, non-mathematical primer on Graph Theory is:

Combinatorics: The Fine Art of Counting

Week 8 Lecture Notes: Graph Theory — MIT

Below is a problem one may want to try. It has historical significance (google "Hamilton's icosian" if you are curious). Hamilton developed it into a child's board game with a circular mahogany board, ivory pegs to insert into the nodes (holes) and twine to string around the pegs to mark the pathways. Hamilton sold all rights to the game for £25 in the 1850's. Today an original game is worth about $500,000. BTW, the Irish-born Hamilton, 1805-1865, may have been the most brilliant mathematician of the 19th century.

The figure itself is just the projection of a Dodecahedron upon a plane.

Question #1: Starting at any node (“dot”) can one progress along the lines around the figure through all the nodes *without passing through the same node twice*?

If so, then one has traced out a Hamiltonian *path*.

Question #2: Can one do the same as above *but return to the same node from which one started*?

If so, then one has traced out a Hamitonian *circuit*.

I won’t say beforehand whether any path or circuit exists.

Have a go!