3色合衆国

TAOCPには, グラフの例として, 連なっている合衆国(contiguous USA)が登場する.

ある演習問題に, 3色塗分け可能な誘導部分グラフを作れというのがあった. そんなにたやすい問題ではない. 解答を見ると意外にも, カリフォルニア州とオハイオ州を除くと, 3色で塗分けられるらしい.

そこまで分かると, 実際の塗分けは, 最初の2つの色を決めれば, その後の色は次々と決るので, あっという間の作業であった.