５色定理

てくますゼミ 2023.06 ミニ講座

Transcript

1. 5色定理
2. 地図に色を塗ろう！ ルール 2つの領域が境界線でとなり合う場合は別の色で塗る。 できるだけ少ない色で塗りきってみよう。
3. 地図に色を塗ろう！ ルール 2つの領域が境界線でとなり合う場合は別の色で塗る。 できるだけ少ない色で塗りきってみよう。
4. 地図に色を塗ろう！ どんな地図でも塗りきれるようにするには、何色あればいいだろうか？ 実は、4色あれば塗りきれるということが知られている！ それは「4色定理」と呼ばれていて、証明はとても難しい…… 5色あれば塗りきれるという「5色定理」の証明はちょうどいい難しさなので、 5色定理の証明に挑戦しよう！
5. ①地図をグラフに対応させる グラフとは、頂点と辺でできた図のこと。 領域を頂点に対応させて、領域がとなり合っているときに対応する頂点を辺で結ぶ。 地図が5色以下で塗りきれることは、グラフの頂点が5色以下で塗りきれることと同じ。 このグラフは1つのかたまりになっていて(連結であるという)、 辺どうしが途中で交差しないように平面に描けていて(平面グラフという)、 2頂点を2つ以上の辺が結んでいたり，辺の両端が同じ頂点を結んでいたりしない(単純であるという)。
6. ②オイラーの多面体定理 連結な平面グラフは、頂点の数を𝑉，辺の数を𝐸，領域の数を𝐹としたとき、次をみたす。 𝑉 − 𝐸 + 𝐹 = 2 凸多面体で成り立つオイラーの多面体定理は、連結平面グラフのことばに置き換えることができる。
7. ③価数5以下の頂点がある 価数とは、その頂点を端点にしている辺の数のこと。 このグラフに価数5以下の頂点がなかったとしたら…… 辺は頂点ごとに6つ以上あり、2回ずつ重複して数えているので、 2𝐸 ≧ 6𝑉 単純なグラフなので、辺は領域ごとに3つ以上あり、2回ずつ重複して数えているので、 2𝐸 ≧ 3𝐹 𝑉 − 𝐸 + 𝐹 ≦ 1 3 𝐸 − 𝐸 + 2 3 𝐸 = 0 となり、オイラーの多面体定理に反してしまう。 よって、このグラフには価数5以下の頂点がある。
8. ④価数5以下の頂点に色を与える 5色以下で塗りきれることを頂点の数に関する数学的帰納法で示そう。 頂点が1個のとき、1色で塗りきれる。 頂点が𝑘個のグラフなら5色で塗りきれると仮定すると…… 頂点が𝑘 + 1個のグラフを考えると、③から価数5以下の頂点があるので𝑣としよう。 𝑣と𝑣を端点にもつ辺を取り除いたグラフは頂点が𝑘個なので5色で塗りきっておく。 (１)𝑣にとなり合う頂点が4色以下で塗られているなら、𝑣を使われていない色で塗ることができる。 𝑣 𝑣 「頂点1つで成り立つ」，「頂点𝑘個で成り立つなら𝑘 + 1個でも成り立つ」を示して、 ドミノ倒しのように頂点いくつでも成り立つことを示す方法。
9. ④価数5以下の頂点に色を与える (２)𝑣にとなり合う頂点が異なる5色で塗られているなら…… 𝑣の価数が5であり、5頂点を時計回りに𝑣1 ，…，𝑣5 として、それらの色を𝑐1 ，…，𝑐5 としよう。 (ⅰ)𝑐1 と𝑐3 で塗られた頂点とそれらを結ぶ辺だけを見たとき、 𝑣1 と𝑣3 が1かたまりになっていないなら、 𝑣3 が含まれているかたまりの𝑐1 と𝑐3 を逆転させた塗り方を考えると、 𝑣を𝑐3 で塗ることができるようになる。 (ⅱ)𝑣1 と𝑣3 が1かたまりになっているなら、 𝑐2 と𝑐4 で塗られた頂点とそれらを結ぶ辺だけを見ると、 𝑣1 と𝑣3 のかたまりを越えることができず、 𝑣2 と𝑣4 は1かたまりにならないので、 𝑣4 が含まれているかたまりの𝑐2 と𝑐4 を逆転させた塗り方を考えると、𝑣を𝑐4 で塗ることができるようになる。 よって、頂点が𝑘 + 1個のグラフも5色で塗りきれる。 数学的帰納法により、頂点がいくつのグラフでも5色で塗りきれる。 𝑣 𝑣1 𝑣2 𝑣3 𝑣4 𝑣5 𝑣 𝑣1 𝑣2 𝑣3 𝑣4 𝑣5 𝑣 𝑣1 𝑣2 𝑣3 𝑣4 𝑣5 (ⅰ) (ⅱ)