Does there exist a Hamiltonian tour of the graph whose vertices are the 48 contiguous United States and whose edges connect states which border each other? More geographically, can you drive through all of the lower 48 states passing through each exactly once? (From 360.)
Here's one possible solution, although I ignored the constraint implicit in the story that provoked the question, which required a start in Michigan. Note that you have to start or end the tour in Maine since it only borders one other state.