The mainland counties of England form a graph with counties as vertices and edges as touching borders. Is there a Hamiltonian path one can take? This is not homework, I just have an idea for a holiday around England where I visit every county only once!
Is there a Hamiltonian path for the graph of English counties?
10
$\begingroup$
graph-theory
-
0@MichaelLugo Your question reminds me of this guy: http://www.barrystiefel.com/50_states_in_a_weeks_vacation/50_states_in_a_weeks_vacation.htm He didn't try to make the path Hamiltonian, however. – 2012-08-01
1 Answers
17
Let's assume we can access the Isle of Wight through Hampshire. Then the answer is yes:
N.B.: This uses ceremonial counties instead of administrative counties; see comments for discussion.
Edit (after a comment below): The background image from Wikipedia. I found the path mostly by luck, with the knowledge that I had to start in the Isle of Wight and finish in Cornwall.
-
0Nice! quick and easy. – 2012-08-01