TOPICS
Search

Contiguous USA Graph


Contiguous USA graph

The "contiguous USA graph" is the graph whose vertices represent the contiguous 48 states of the United States plus the District of Columbia (DC) and whose edges connect pairs of states (plus DC) that are connected by at least one drivable road (Knuth 2008, p. 15).

This graph has 49 vertices and 107 edges. It is a planar, bridged (the only bridge being the edge between New Hampshire and Maine), identity graph and is nonhamiltonian but traceable.

The following table lists the states by vertex degree (i.e., number of other states to which they're connected).

dstates
1ME
2DC, FL, RI, SC, WA
3CA, CT, DE, LA, MI, ND, NH, NJ, VT
4AL, AZ, IN, KS, MN, MS, MT, NC, NM, OR, TX, WI
5GA, IL, MA, MD, NV, NY, OH, UT, WV
6AR, CO, IA, ID, NE, OK, PA, SD, VA, WY
7KY
8MO, TN
ContiguousUSAGraphColorings

The contiguous USA graph has chromatic number 4 and fractional chromatic number 7/2, with corresponding minimal colorings illustrated above (S. Wagon, pers. comm., Dec. 8, 2011).

GracefulPi-Way

Rather amazingly, the contiguous USA graph is graceful, as illustrated above. More amazingly still, in what Knuth (2024, p. 18) describes as a "graceful miracle," as found by T. Rokicki in October 2020, the above graceful labeling has the property that the 15 states on the western and northern borders stretching from California to Maine are labeled with the numbers 31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64, 33, 83, and 27, which are precisely the first 30 decimal digits of pi! With apologies to Gordon Lightfoot's "Carefree Highway," this path (shown in red above) might be termed the "graceful pi-way."


See also

Four-Color Problem, Graceful Pi-Way

Explore with Wolfram|Alpha

References

Knuth, D. E. The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Functions and Boolean Functions. Upper Saddle River, NJ: Addison-Wesley, p. 15, 2008.Knuth, D. E. §7.2.2.3 in The Art of Computer Programming, Vol. 4. Pre-Fascicle 7A, Dec. 5, 2024.Knuth, D. E. "Download contiguous-usa.dat, Adjacencies Between the Contiguous United States and DC." https://www-cs-faculty.stanford.edu/~knuth/contiguous-usa.dat.

Referenced on Wolfram|Alpha

Contiguous USA Graph

Cite this as:

Weisstein, Eric W. "Contiguous USA Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ContiguousUSAGraph.html

Subject classifications