I typed in a list of which US states border which other US states, so I can write programs to do various things with it. For instance by creating an adjacency matrix and raising it to successive powers, I was able to determine which states are furthest apart in the sense that you have to cross the most borders to get between them without leaving the US. (Maine to either Washington or Oregon requires at least 12 state border crossings. That's the record, unless you count the two states that can't be reached at all.) I thought I had found the record in-alphabetic-order trip, IA IL IN KY MO TN VA WV, until I realized that I was doing alphabetic order by state *abbreviation*. Oops! The longest trips by alphabetic order are shorter than that. I'll leave them to others to rediscover -- or to try longest trip by states in order of population, area, or anything else quantifiable. I only ran into trouble when attempting to verify that the list was correct. Well, not correct, necessarily, but consistent. Of course I made sure that if A borders B then B border A, and that no state borders itself. But what about impossible maps? Or, to put it in mathematical terms, a non-planar graph? This turns out to be surprisingly hard. I'm familiar with Kuratowski's theorem, but I estimate it would take at least a month of CPU time to test every possible set of 5 or 6 states. (No, applying it only to states that border each other is invalid.) And for larger maps, it would be completely infeasible. Of course I want any software I write to work with any map, not just with this map. My first thought was that the states that border a given state should always be able to be put into a circular order. If A borders B, there should always be exactly two states that border both A and B. If I start with one of them and look at states that border A and this new state, I should keep getting a succession of different states that border A, until I return to B, and there should be no bordering states unaccounted for or duplicated. For instance Tennessee (which is tied for the record of most bordering states) borders my home state of Virginia. Those two states border Kentucky. Tennessee and Kentucky both border Missouri. Tennessee and Missouri both border Arkansas. Tennessee and Arkansas both border Mississippi. Tennessee and Mississippi both border Alabama. Tennessee and Alabama both border Georgia. Tennessee and Georgia both border North Carolina. Tennessee and North Carolina both border Virginia, and we're back where we started, with no states listed as bordering Tennessee unaccounted for, nor any appearing twice. Of course we run into a problem with a state on the border of the country. But we can create a new "state," the Exterior. I also added Lake Michigan and Four Corners as "states," so that every border ends on another border. It didn't work. Sometimes the same state shows up twice when going around the border of a state. For instance Virginia borders Maryland twice, once on each side of DC. New York borders the Exterior twice. Whenever that happens, it can only be because one or more states are enclosed by state A and the twice-bordering state B. Maryland and Virginia enclose DC. New York and the Exterior enclose all the New England states. To find these enclosed states, I zero the rows and columns representing the two enclosing states from the adjacency matrix, completely delete the rows and columns representing Alaska and Hawaii, and raise the matrix to successive powers. If all the zeros (other than in the two rows and columns I zeroed) go away, then there's an inconsistency, a "tunnel" from the enclosed states to the rest of the world. Otherwise, I regard the states which have more than half of their rows as persistent zeros as being enclosed. (Since there are an even number of states, I could in principle get a tie, where exactly half the states are on one side of the "wall" created by the two states in question and exactly half are on the other. In that case every row would be exactly half zeros and I'd have to make an arbitrary choice which is inside and which is outside. I don't want to privilege the Exterior; I'd prefer to treat every state the same. Anyhow, the Exterior may be one of the two enclosing states.) (It just occured to me that in principle there could be any number of enclosures by the two states in question, and if there are enough of them they could all be very small. Sigh.) This works. But sometimes *three* states enclose a set of states. And doing the same thing with three states doesn't work. For instance it claims that Maryland, Virginia, and West Virginia surround DC, and that's not the case, as West Virginia does not border DC. I think I can make it work if I keep track of what any two of those three states enclose, and deal with that somehow. But what a pain. Anyhow, I'm not at all convinced that what I'm doing would prove consistency anyway, rather than just finding one possible failure mode. Here's my list, if anyone else wants to play with it: AK: EX AL: EX FL GA MS TN AR: LA MO MS OK TN TX AZ: CA EX FC NM NV UT CA: AZ EX NV OR CO: FC KS NE NM OK UT WY CT: EX MA NY RI DC: MD VA DE: EX MD NJ PA EX: AK AL AZ CA CT DE FL GA HI ID LA MA MD ME MI MN MS MT NC ND NH NJ NM NY OH OR PA RI SC TX VA VT WA WI FC: AZ CO NM UT FL: AL EX GA GA: AL EX FL NC SC TN HI: EX IA: IL MN MO NE SD WI ID: EX MT NV OR UT WA WY IL: IA IN KY LM MO WI IN: IL KY LM MI OH KS: CO MO NE OK KY: IL IN MO OH TN VA WV LA: AR EX MS TX LM: IL IN MI WI MA: CT EX NH NY RI VT MD: DC DE EX PA VA WV ME: EX NH MI: EX IN LM OH WI MN: EX IA ND SD WI MO: AR IA IL KS KY NE OK TN MS: AL AR EX LA TN MT: EX ID ND SD WY NC: EX GA SC TN VA ND: EX MN MT SD NE: CO IA KS MO SD WY NH: EX MA ME VT NJ: DE EX NY PA NM: AZ CO EX FC OK TX NV: AZ CA ID OR UT NY: CT EX MA NJ PA VT OH: EX IN KY MI PA WV OK: AR CO KS MO NM TX OR: CA EX ID NV WA PA: DE EX MD NJ NY OH WV RI: CT EX MA SC: EX GA NC SD: IA MN MT ND NE WY TN: AL AR GA KY MO MS NC VA TX: AR EX LA NM OK UT: AZ CO FC ID NV WY VA: DC EX KY MD NC TN WV VT: EX MA NH NY WA: EX ID OR WI: EX IA IL LM MI MN WV: KY MD OH PA VA WY: CO ID MT NE SD UT (Watch out that your mail reader doesn't break the long line "EX.") Also feel free to post other "maps" in the same format, either maps of real places or perverse maps designed to stress-test software, perhaps with hidden inconsistencies.