THE POSTAL UNION
by Ross Eckler
Word Ways, 1997
In his first column as Kickshaws editor in February 1989, Dave Morice showed how one could construct chains of state names using their postal codes: for example, MaINe contains the bigram IN which stand for Indiana, INDiana contains the bigram ND which stands for North Dakota, North DAKota contains the bigram which stands for ALAska, and so on. Recently, I realized that this is an example of a directed graph which I discussed in another context in "Directed Word Chains (Part 1)" in the August 1991 Word Ways.
A directed word graph is like a structure of one-way streets joining different cities--you can drive from city A to city B but not the re-verse. Some cities can only be entered at the start of a tour, and others cannot be left once you reach them.
What does the postal union graph look like? There is a group of eight states called the core, the members of which are called insiders; any state can be reached from any other by some path inside the core. The core consists of a cycle consisting of seven states:
-north dAKota-ALaska-aLAbama-louisIAna-ioWA-washINgton-iNDiana-
together with the two-state cycle -wasHIngton-haWAii-. In addition, one can shortcut aLAska-louisIAna, and double back indIAna-ioWA.
There are a large number of states that feed into the core, consisting of starters (states which cannot be reached from any other one) and preceders (states joining starters to the core). There are 20 of the former and eight of the latter (CA DE GA ME MI MO RI VA):
south dAKota
pennsylvanIA (also pennsylVAnia-virgINIA)
neVAda-virgINIA
west virgINIA
new hampsHIre
north carolINa (also north CArolina-cALifornIA)
south carolINa (also south CArolina-cALifornIA)
wisconsIN (also wiSConsin-south carolINa)
wyomING (also wyoMIng-michiGAn-georgIA, wyoMIng-micHIgan)
oHIo
mINnesota (also MInnesota-michiGAn-georgIA, MInnesota-micHIgan)
illINois
MIssissippi-micHIgan (also MIssissippi-michiGAn-georgIA)
verMOnt-MIssouri-micHIgan (also verMOnt-MIssouri-michiGAn-georgIA,
verMOnt-rhoDE island-deLAWAre, also verMOnt-missouRI-rhode isLAND)
MOntana-MIssouri-micHIgan (also MOntana-MIssouri-michiGAn-georgIA,
MOntana-rhoDE island-deLAWAre, also MOntana-missouRI-rhode isLAND)
okLAhoma
maryLAND
aRIzona-rhode isLAND (or aRIzona-rhoDE island-deLAWAre)
floRIda-rhode isLAND (or floRIda-rhoDE island-deLAWAre)
new MExico-maINe
However, only two of the eight insiders can be used to exit the core, and both lead at once to enders (states which cannot be exited):
alabaMA-massachusetts
nORth dakota-oregon
The other enders are kansas, idaho, utah, nebraska and arkansas. TenNEssee, NEw jersey, NEw york, NEw hampshire, NEw mexico and maiNE feed into nebraska; connecticUT, soUTh dakota and soUTh carolina into utah; MAryland, MAine and oklahoMA into massachusetts; and florIDa into idaho. FlORIDa is the state that connects with the most enders: directly to oregon and idaho, through the core to massachusetts, and to arkansas via rhoDE island and delawARe. Oregon can be reached from the largest number of other states, 38: directly from colORado, califORnia, geORgia, new yORk, nORth carolina, nORth dakota and flORida, and indirectly (via the core) for the other starters and preceders mentioned previously.
Colorado is a most unusual state. It is neither a starter nor an ender, nor can one reach it from the core, or go to the core from it. All it does is connect starters (COnnecticut, newmexiCO, wisCOnsin) to an ender (oregon). The name given to such an entity is a bypasser.
There are three states--kansas, texas, kentucky--that are simultaneously starters and enders (and hence isolanos).
What is the longest tour that one can make without revisiting any state? The answer is probably FL(or AZ)-RI-DE-LA-IA-WA-IN-ND-AK-AL-MA and VT(or MT)-MO-MI-GA-IA-WA-IN-ND-AK-AL-MA. And if a beginner can be linked to an ender, what is the minimum number of linking statenames needed to do it? What is the maximum value of this number, taken over all beginner-ender pairs? (This is called the span of the graph.) It seems likely that the two "farthest apart" states are the real-life neighbors verMOnt and massachusetts, connected by intermediate states MIssouri, micHIgan, haWAii, washINgton, iNDiana, north dAKo-ta, ALaska, and alabaMA.