たとえば、大きな島を $n$ 個に分けろということになった場合、その形や方角なんかを無視して、何パターンの地図が描けるかという問題。
四色問題以前
四色問題ではグラフ理論な話に持ち込むが、ここでもその技法を流用することにする。それは、それぞれの国に頂点を対応させ、隣接する国同士を辺で結ぶという操作を行うことである。たとえばこんな感じ。
黒線で囲まれた領域を赤で示したグラフに置き換える。ありがとう Inkscape。
レソト
では 2 つに分ける場合を考える。ここで考えるグラフは次のようなものであろう。
2 つの領域が隣接しているのは次の場合だけか。
いや、そうではない。次のように、南アフリカの中にレソトがあるように、ある領域内に別の領域がすっぽりと含まれている場合も考えられる。包領というらしい。
これは困ったね、ということで、海（あるいは一般に周囲のどうでもいい領域）を追加してやろう。ということで、青い部分が新たに追加された。
前者のパターンについては両国が海に接している。
後者については南アフリカが海に接しているが、レソトは海に接していないということを表せる。
$n=2$ の場合、この 2 パターンのみがある。
今回のまとめ
- 国を点、国同士の隣接関係を辺としてグラフで表す
- 海を表す点を用意し、それぞれの国の海との隣接関係も辺とする
- $n$ 個の国を考える場合、1 つの海を加えて、合計 $n+1$ 個の点が現れる
