四色定理を(コンピュータなしで)証明する

証明の概略
step1. 平面グラフの性質
step2. 平面グラフの4彩色可能問題(四色問題)の証明
おまけ(真部分グラフに最小彩色数がnのグラフを含まない最小彩色数がnのグラフが$K_{n}$であることの厳正な証明)
　ここで、補題1より、"最小彩色数が$n$である$ \Longleftrightarrow$$n-1$部グラフ(の部分グラフ)でない$n$部グラフ(の部分グラフ)である"ので、そちらを示す。

大学数学基礎解説

四色定理を(コンピュータなしで)証明する

四色定理,グラフ理論,証明

1353

　初めまして、12匁です。
　本記事は初投稿の文書なので杜撰かと思いますが大目に見てもらえると嬉しいです。また、本記事を読むうえで グラフ理論 の予備知識が必要なのでそこはご容赦ください。

証明の概略

平面グラフの性質
1. 部分グラフとして含む完全グラフ
2. 完全グラフを含まない $⟹$ 4彩色可能
平面グラフの4彩色可能問題(四色問題)の証明

step1. 平面グラフの性質

　平面グラフは $K_{5}$ を部分グラフとして含まないことはよく知られている。
また、 $K_{3, 3}$ を部分グラフとして含まないことも知られているが、今回の証明には登場しないので忘れてもらっていい。
　また、平面グラフは頂点の個数だけ色を準備すれば彩色可能なので、"最小彩色数"が存在するはず。(最小彩色数が4以下 $⟺$ 4彩色可能)

　では、平面グラフはどのような完全グラフを部分グラフとして含む(含まない)のだろうか。

　平面グラフは $K_{5}$ を部分グラフとして含まないので、そこから $K_{6}$ , $K_{7}$ , $\dots$ も含まないことが推測できる。一応証明しておこう。

対偶をとると、" $K_{n > 5}$ を含む $⟹$ $K_{5}$ を含む"となる。
そもそも $K_{n > 5}$ は $K_{5}$ を含むので自明である。

　以上より、平面グラフは $K_{n \geq 5}$ を部分グラフとして含まないことが分かった。

　また、" $K_{n}$ を含まない $⟹$ 最小彩色数がnの部分グラフを含まない"である。これもしっかり証明しておこう。

対偶をとると、"最小彩色数が $n$ の部分グラフを含む $⟹$ $K_{n}$ を含む"となる。
最小彩色数が $n$ の部分グラフのうち最小なものを $g$ とおくと、それは"真部分グラフに最小彩色数が $n$ のグラフを含まない最小彩色数が $n$ のグラフ"となり、それは $K_{n}$ である。

　よって、平面グラフは"最小彩色数が5以上の部分グラフを含まない"ことが分かった。つまり、"最小彩色数が4以下の部分グラフしか含まない"ことが導かれた。

step2. 平面グラフの4彩色可能問題(四色問題)の証明

　step1で、平面グラフは最小彩色数が4以下の部分グラフしか含まないことが分かった。
　ここで、"自分自身"も自身の部分グラフであることを思い出すと次の定理を得る。

4彩色可能定理

平面グラフは最小彩色数が4以下である。

　これは、まさに私たちの示したかったことだ。こうやって考えることで平面グラフは4彩色可能だということを論理的に示すことができるのである。

おまけ(真部分グラフに最小彩色数がnのグラフを含まない最小彩色数がnのグラフが $K_{n}$ であることの厳正な証明)

step1で、「"真部分グラフに最小彩色数がnのグラフを含まない最小彩色数がnのグラフ"となり、それは $K_{n}$ である。」と述べたが、にわかには信じがたいことである。なのでここでしっかり証明する。

彩色可能をグラフで表す

$g$ が $n$ 彩色可能 $⟺$ $g$ は $n$ 部グラフの部分グラフである。

※n部グラフは2部グラフを一般化したものと思ってもらっていい

" $⟸$ "は自明なので" $⟹$ "のみを示す。
$g$ が $n$ 彩色可能ということは、同じ色どうしを同値類に属させれば $g$ は単純グラフとしていいので $n$ 部グラフの部分グラフになる。

帰納法の準備

" $s$ 部グラフでない $s + 1$ 部グラフ"は
" $s - 1$ 部グラフでない $s$ 部グラフ"を含む

　対偶を示す。(" $s - 1$ 部グラフでない $s$ 部グラフ"を含まない $⟹$ " $s$ 部グラフでない $s + 1$ 部グラフ"でない)
　場合分けをする。

左側が $t \neq s + 1$ 部グラフのとき

　自明。(ヴェン図を考えるといい。)

左側が $s + 1$ 部グラフのとき

　部分グラフとして $s$ 部グラフを含むが、それらはすべて $s - 1$ 部グラフと換えられ、部分グラフとして含む $s + 1$ 部グラフが $s$ 部グラフになってしまう。自身( $s + 1$ 部グラフ)は部分グラフとして含むので、「 $s$ 部グラフでない $s + 1$ 部グラフ」という条件を満たしていない。

以下、数学的帰納法を用いて、真部分グラフに最小彩色数がnのグラフを含まない最小彩色数が $n$ のグラフが $K_{n}$ であることを証明する。

　"真部分グラフに最小彩色数が $n$ のグラフを含まない最小彩色数が $n$ のグラフ"が $K_{n}$ であるということは、__最小彩色数が $n$ のグラフは必ず $K_{n}$ を含む__と言い換えられる(同値である)。

　ここで、補題1より、"最小彩色数が $n$ である $⟺$ $n - 1$ 部グラフ(の部分グラフ)でない $n$ 部グラフ(の部分グラフ)である"ので、そちらを示す。

$n = 2$ の場合

　1部グラフ(孤立点のみのグラフ)でない2部グラフは必ず辺を含むはず。よって、そのグラフは $K_{2}$ を含む。

$k$ を仮定し、 $k + 1$ を導く

　 $k - 1$ 部グラフでない $k$ 部グラフは $K_{k}$ を含むと仮定する。
そのとき、補題3より、" $k$ 部グラフでない $k + 1$ 部グラフ"は" $k - 1$ 部グラフでない $k$ 部グラフ"を含むことになり、仮定より $K_{k}$ を含むとわかる。
　 $k$ 部グラフでない $k + 1$ 部グラフが $K_{k}$ を含むとき、(その) $K_{k}$ (のうちのどれか一つ)に用いられていない同値類を $C (v)$ と置くと、 $\forall v \in C (v)$ が $K_{k}$ と完全に結ばれていないと仮定すると $\dots (*)$ 、 $v$ と結ばれていない $K_{k}$ の頂点を同じ同値類に入れることができるため、 $k$ 部グラフになってしまい矛盾する。
　よって仮定 $(*)$ が間違っていることとなり、 $K_{k}$ と完全に結ばれている $v \in C (v)$ が存在することがわかる。そして $\exists v \in C (v)$ と $K_{k}$ を完全に結んだグラフは $K_{k + 1}$ である。

　よって題意は示された。(証明終わり)

　おまけなのにとても苦しい内容になってしまい、すみません。間違い等の指摘があり次第再投稿を検討します。

　最後となりますが、ここまでのお付き合いありがとうございました。またどこかで会いましょう。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　by 12匁

投稿日：2023年1月2日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

12匁

1779

直和の定義見て"集合として等しい"を知らずに背伸びしていたことに気づいたことがある。

他の人のコメント

コメントはありません。

読み込み中

12匁

四色定理を(コンピュータなしで)証明する

証明の概略
step1. 平面グラフの性質
step2. 平面グラフの4彩色可能問題(四色問題)の証明
おまけ(真部分グラフに最小彩色数がnのグラフを含まない最小彩色数がnのグラフが$K_{n}$であることの厳正な証明)
　ここで、補題1より、"最小彩色数が$n$である$ \Longleftrightarrow$$n-1$部グラフ(の部分グラフ)でない$n$部グラフ(の部分グラフ)である"ので、そちらを示す。

四色定理を(コンピュータなしで)証明する

証明の概略

step1. 平面グラフの性質

step2. 平面グラフの4彩色可能問題(四色問題)の証明

おまけ(真部分グラフに最小彩色数がnのグラフを含まない最小彩色数がnのグラフがKnであることの厳正な証明)

左側がt≠s+1部グラフのとき

左側がs+1部グラフのとき

以下、数学的帰納法を用いて、__真部分グラフに最小彩色数がnのグラフを含まない最小彩色数がnのグラフ__がKnであることを証明する。

ここで、補題1より、"最小彩色数がnである⟺n−1部グラフ(の部分グラフ)でないn部グラフ(の部分グラフ)である"ので、そちらを示す。

n=2の場合

kを仮定し、k+1を導く

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

おまけ(真部分グラフに最小彩色数がnのグラフを含まない最小彩色数がnのグラフが $K_{n}$ であることの厳正な証明)

左側が $t \neq s + 1$ 部グラフのとき

左側が $s + 1$ 部グラフのとき

以下、数学的帰納法を用いて、真部分グラフに最小彩色数がnのグラフを含まない最小彩色数が $n$ のグラフが $K_{n}$ であることを証明する。

　ここで、補題1より、"最小彩色数が $n$ である $⟺$ $n - 1$ 部グラフ(の部分グラフ)でない $n$ 部グラフ(の部分グラフ)である"ので、そちらを示す。

$n = 2$ の場合

$k$ を仮定し、 $k + 1$ を導く