geography, graph theory and insomnia

Sometimes if I am bored or trying vainly to fall asleep I'll start running through lists in my head. One such list is the fifty states.

I never memorized the states in alphabetical order. Rather, I picture a map and draw a path in my head, going from state to state. Starting in Maine, my mentally-created path goes the\rough each of the lower 48 states without visiting any twice, and ends in Washington. After that I add Alaska and Hawaii.

But this has gotten me to thinking about how many different paths there are through the lower 48 so that each state is visited once and only once. I suppose it's an exercise in graph theory. Or brute force enumeration.

Sadly, while I have enough interest to wonder about it, I don't have enough interest to actually figure it out. That is something I leave to the reader.

But I have gleaned a few insights:

• Since Maine only borders one state (New Hampshire), it has to come first or last. For the rest of this discussion, I will assume it comes last -- each path in which Maine comes last has a direct analog in which Maine comes first. Since New England only borders New York, the path has to go through all of the New England states first, and then enter New York. A little analysis should convince you that any path must start with Maine, New Hampshire, Vermont, Massachusetts, Rhode Island, Connecticut, New York.
• Since South Carolina only borders North Carolina and Georgia, any path that doesn't end in South Carolina must contain the sequence: North Carolina, South Carolina, Georgia (or its reverse).
• Since Florida only borders Georgia and Alabama, any path that doesn't end in Florida must contain the sequence: Georgia, Florida, Alabama (or its reverse).
• The above two notes imply that any path must:
• end in South Carolina;
• end in Florida; or
• contain the sequence: North Carolina, South Carolina, Georgia, Florida, Alabama (or its reverse)
• Since Washington only borders Oregon and Idaho, any path that doesn't end in Washington must contain the sequence: Oregon, Washington, Idaho (or its reverse).

Happy trailblazing.