The Wagon USA map graph is the planar graph representing the adjacency relation of the 48 contiguous states of the United States, Lake Michigan, and the entire exterior region in Wagon's map (Wagon 2010a, pp. 464-465). Two regions are adjacent when they share a boundary line segment rather than just a point. Michigan is treated as a single region. The graph provides a geographic example of the tangling of Kempe chains in the faulty argument underlying Kempe's coloring algorithm.
The state portion is the contiguous USA graph with the District of Columbia removed and has 48 vertices and 105 edges. Add a vertex for Lake Michigan adjacent to Illinois, Indiana, Michigan, and Wisconsin. Add another vertex, labeled Ocean, for the entire exterior region. Its 32 neighbors are Alabama, Arizona, California, Connecticut, Delaware, Florida, Georgia, Idaho, Louisiana, Massachusetts, Maryland, Maine, Michigan, Minnesota, Mississippi, Montana, North Carolina, North Dakota, New Hampshire, New Jersey, New Mexico, New York, Ohio, Oregon, Pennsylvania, Rhode Island, South Carolina, Texas, Virginia, Vermont, Washington, and Wisconsin. There is no edge between Ocean and Lake Michigan. Ocean includes the space beyond Canada and Mexico and is not restricted to actual ocean coastline.
The resulting graph has vertex count 50 and edge count 141. Its chromatic
number is exactly 4. A proper coloring with
four colors exists, and Ocean, Alabama, Florida, and Georgia induce the complete
graph 
,
so fewer colors cannot suffice.
Gethner et al. (2009, p. 264) report Wagon's discovery of a labeling that produces a Kempe impasse at Illinois. A concrete tangle can be exhibited after removing Iowa and leaving Illinois uncolored. In cyclic order around Illinois, Lake Michigan, Wisconsin, Missouri, Kentucky, and Indiana have colors green, red, green, blue, and yellow in a partial proper coloring. A red-blue Kempe chain connects Wisconsin to Kentucky and a red-yellow Kempe chain connects Wisconsin to Indiana. Interchanging green and blue on the Kempe chain containing Lake Michigan and then interchanging green and yellow on the recomputed Kempe chain containing Missouri gives Indiana the color green. Thus the two interchanges do not free green for Illinois. This tangle demonstrates a flaw in the two-interchange argument. Its existence alone does not establish that a particular greedy ordering reaches this partial proper coloring or that the Kempe-Kittell coloring algorithm fails to color the graph.
The Wagon USA map graph is implemented in the Wolfram Language as GraphData["WagonUSAMapGraph"].
