10
$\begingroup$

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!

  • 0
    What would you consider the [Isle of Wight](http://en.wikipedia.org/wiki/Isle_of_Wight) adjacent to?2012-08-01
  • 4
    Your user name suggests that you have a different goal :)2012-08-01
  • 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.2012-08-01
  • 0
    Is there a Hamiltonian path for the 48 contiguous US states? (It would have to start or end in Maine.)2012-08-01
  • 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 1

17

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.

  • 0
    I take this this is the [ceremonial counties](http://en.wikipedia.org/wiki/Ceremonial_counties_of_England) rather than [counties](http://en.wikipedia.org/wiki/Counties_of_england)?2012-08-01
  • 0
    @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.)2012-08-01
  • 0
    Thankyou. I wasn't actually considering Isle of Wight, but this is perfect!2012-08-01
  • 0
    @EulerianHoliday: Fair enough, in that case just start (or finish) in Hampshire!2012-08-01
  • 0
    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.2012-08-01
  • 0
    @Mitch: The image (without vertices and edges) is the one from the Wikipedia page linked to in the OP; the vertices and edges are my doing, and done by hand by a series of lucky guesses (knowing that I had to start in the Isle of Wight and finish in Cornwall).2012-08-01
  • 0
    Nice! quick and easy.2012-08-01