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 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).
The following table lists the states by vertex degree (i.e., number of other states to which they're connected).
states | |
1 | ME |
2 | DC, FL, RI, SC, WA |
3 | CA, CT, DE, LA, MI, ND, NH, NJ, VT |
4 | AL, AZ, IN, KS, MN, MS, MT, NC, NM, OR, TX, WI |
5 | GA, IL, MA, MD, NV, NY, OH, UT, WV |
6 | AR, CO, IA, ID, NE, OK, PA, SD, VA, WY |
7 | KY |
8 | MO, TN |