Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 10 down vote favorite

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!

share|improve this question
What would you consider the Isle of Wight adjacent to? – Arthur Fischer♦ Aug 1 '12 at 16:05
4  
Your user name suggests that you have a different goal :) – t.b. Aug 1 '12 at 16:11
2  
Do you want to get back home at the end of your holiday? That would be a Hamiltonian cycle, not a path. There is clearly no cycle, because Cornwall only borders Devon. – David Speyer Aug 1 '12 at 16:14
Is there a Hamiltonian path for the 48 contiguous US states? (It would have to start or end in Maine.) – Michael Lugo Aug 1 '12 at 19:56
@MichaelLugo Your question reminds me of this guy: barrystiefel.com/50_states_in_a_weeks_vacation/… He didn't try to make the path Hamiltonian, however. – Byron Schmuland Aug 1 '12 at 20:28

1 Answer

up vote 17 down vote accepted

Let's assume we can access the Isle of Wight through Hampshire. Then the answer is yes:

enter image description here

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.

share|improve this answer
I take this this is the ceremonial counties rather than counties? – Chris Taylor Aug 1 '12 at 16:28
@Chris: Yes, but at the same time, when I'm in York I don't see myself as being in a different county from when I'm in Harrogate! (And a tourist certainly wouldn't.) – Clive Newstead Aug 1 '12 at 16:34
Thankyou. I wasn't actually considering Isle of Wight, but this is perfect! – EulerianHoliday Aug 1 '12 at 17:03
@EulerianHoliday: Fair enough, in that case just start (or finish) in Hampshire! – Clive Newstead Aug 1 '12 at 17:05
Kudos...but magic trick over. Now you have to tell us how you did that. By hand or by running algorithm (if so then by what system)? And also, how did you create such a nice picture? You lifted it somewhere? There's no shame in that, but at least give a link. – Mitch Aug 1 '12 at 19:25
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.