日常の悩みを解決するブログ毎日のふとした困り事。その解決法がここにあるかもしれません。・四色問題(四色定理)とは何か?・塗り絵パズルのコツ・四色問題の歴史について触れました。読まれていない方は、まずそちらの記事からお読みになってくださいね。証明を行うためには、いくつかの予備知識が必要になりますので、まずはそれらの用語や定理について解説したいと思います。双対グラフ(そうついぐらふ)四色問題の証明を考える際、実際の塗り絵や地図を使って考えると分かりにくいんですよ。そこで、「双対グラフ」というものを利用して、色の塗り分けを考えていきます。双対グラフとは、塗り絵の中の面を頂点に置き換え、隣り合う面同士は頂点を辺で結ぶことで表したグラフのことです。具体例を挙げると、たとえば上のような塗り絵があったとします。(図1)この塗り絵の中の面に頂点を対応させ、隣り合う面は辺で結びます。(図2)こうしてできた双対グラフに対し、辺で結ばれた頂点は互いに異なる色になるように塗り分けます。(図3)頂点の塗り分けができた双対グラフを元に戻せば、見事に塗り絵が完成します。(図4)双対グラフがいかに便利なものか、ご理解いただけたでしょうか。「グラフ上の辺で結ばれた頂点を異なる色で塗る」という問題に置き換えて考えることができるようになるのです。以下、四色問題の証明は、この双対グラフを用いて話を進めていきます。平面グラフと平面的グラフ平面グラフとは、頂点以外で辺が交わらないグラフのことです。平面的グラフとは、頂点以外で辺が交わっているが、辺を動かして平面グラフに描き直すことができるグラフです。ちなみに、グラフ理論ではグラフを描くことを「埋め込む」というので、以下この言葉を使用していきます。それでは早速具体例を見ていきましょう。上のグラフは頂点以外で辺が交わってしまっていますので、平面グラフではありません。(図5)しかし、交わっている辺を(頂点にくっ付けたまま)うまく動かしてあげれば...平面グラフに埋め込むことができました!(図6)辺を動かすときのポイントですが、辺がゴムのような柔らかい素材でできていると考えるとイメージしやすいと思います。図5は平面グラフではないが、平面的グラフではあったわけです。次のグラフはどうでしょうか?(図7)これは、最後の1本(黄色の辺)をどのように動かしても他の辺と交わってしまうので、平面グラフに埋め込むことができません。(図8)したがって、このグラフは平面的グラフではないことが分かります。塗り絵や地図の双対グラフは、平面グラフになるということです。「塗り絵や地図は平面だから」です。「どんな平面グラフの頂点も4色で塗り分けられるか」という問題に置き換えて考えることができるのです。オイラーの多面体定理オイラーの多面体定理とは、以下のような定理です。