- In Bulgarian courtesy of Rico Nizzo.
- In Finnish courtesy of Elsa Jansson.
- In French courtesy of David Wardell.
- In German courtesy of Philip Egger.
- In Indonesian courtesy of Jordan Silaen at ChameleonJohn.com.
- In Italian courtesy of Emfurn.
- In Macedonian courtesy of Elena Simski.
- In Polish courtesy of Marek Murawski.
- In Romanian courtesy of Irinia Vasilescu.
- In Russian courtesy of Hum2D.
- In Tamal courtesy of Vikatan.com.

Here we show a few examples, using the graph representing the 48 contiguous states, with a node for each state, and an edge between two states if they share a border. For each of the maps, if you click on the image you will reach the source document in SVG format. Here is the graph, locating the nodes at the capitals of the states:

Based on a simple analysis, plus Knuth's efforts, we can say the following:

- All tours must start or end in Maine, since Maine has only a single neighbor. We will use Maine as the starting point.
- All tours must end beyond New York, since it is an articulation point.
- There are 68,656,026 different capital tours overall.

Here is the longest capital tour, totalling 18,040 miles:

Since a BDD encodes all possible solutions to a Boolean formula, we can easily compute how many solutions there are. For graph coloring, we adjust our counts to eliminate symmetries due to the arbitrary assignment of color values (4! symmetric cases for 4-coloring).

For coloring the contiguous 48 states, there are 533,816,322,048 possible colorings. (This is 1/2 the number reported by Knuth, since his map includes Washington, DC as a 49th “state,” and it can be assigned either of the two colors not used for Maryland and Virginia.) Here are some interesting examples of special colorings:

- A balanced coloring, in which each color is used for exactly 12 states. There are 12,554,677,864 such colorings, which is a surprisingly high 2.4% of all possible colorings.
- An unbalanced coloring, in which one of the colors (green) is used as little as possible (2 states). There are just 288 ways to color the map such that one color gets used just twice.
- An unbalanced coloring, in which one of the colors (yellow) is used as much as possible (18 states). There are 71,002,368 ways to color the map such that one color gets used 18 times.
- Combining both. Colorings using the colors 2, 13, 15, and 18 times. This sequence 1) from left to right, uses each color in succession for the fewest possible number of times, and 2) from right to left, uses each color in succession for the most possible number of times. There are 24 such solutions.

From the perspective of graph coloring programs, the map of the US 48 states is fairly simple. For a more challenging map, see the web page on the McGregor Graph.

Randal E. Bryant Last modified: Tue Jan 19 07:48:18 EST 2010