0

四色定理のパズル的証明(訂正版)

127
2
$$$$
報告

 以前投稿した記事にて、論理の根幹的な部分に間違いが発見されたため今回のような形で記事を再投稿させていただきました。また、指摘をくださったユーザーの方々に、この場で感謝させていただきます。ありがとうございました。

本題

 では、四色定理を証明していこう。

定義

 今回、四色定理を証明するにあたって(説明を簡略化するために)いくつかの定義をしていく。

$n$部グラフ

 $2$部グラフを一般化した、"$n$つの類からなるグラフ"のこと。
また、同じ類に属している$2$頂点は隣接してはいけない。

色の同値類

 グラフを$n$色で彩色するとき、"同じ色"という観点で類を作れる。
そして、その類は同値律が成り立つ(証明略)。よってその類を"色の同値類"と呼ぶ($n$部グラフの類と混濁しないために"同値類"とした)。

($n$部グラフの)類と隣接する

 頂点$v$$n$部グラフの類$C(x)$の元と隣接しているとき、
"$v$$C(x)$と隣接している"という。

準完全頂点

 $n$部グラフにおいて、自分の属している類以外の全ての類と隣接している頂点。

準完全$n$部グラフ

 準完全頂点のみからなる$n$部グラフ。

彩色数

 グラフを彩色する際に用いた色の個数(色の同値類の個数)。

最小彩色数

 彩色数の中で最小なもの。

定義は以上で終わる。

証明

大きく$3$ステップに分かれる。

   平面グラフ
$\Longrightarrow K_{n\geq5}$をマイナーとして含まない $\cdots$step1
$\Longrightarrow$最小彩色数が$5$以下でない     $\cdots$step2
$\Longrightarrow 4$彩色可能           $\cdots$step3

step1

 クラトフスキーの定理より、平面グラフは$K_{5}$をマイナーとして含まない。
 $K_{5}$をマイナーとして含まないならば$K_{n\geq5}$もマイナーとして含まない。

 以前投稿した記事の中で、クラトフスキーの定理を間違えて提示してしまった。"マイナー"という概念やクラトフスキーの定理については、読者諸君が各々調べてほしい。

step2

 まずは幾つか補題を示す。

$n$彩色可能$\Longleftrightarrow$$n$部グラフである

 グラフ$g$$n$彩色とすると、色の同値類が$n$個できるが、その色の同値類を$n$部グラフの類とみなすと、$n$部グラフになる。
 逆に、$n$部グラフの類ごとに彩色すれば$n$彩色可能である。

 最小彩色数が$n \Longleftrightarrow (n-1)$部グラフでない$n$部グラフである

 最小彩色数が$n \Longleftrightarrow \lnot${$(n-1) $彩色可能 }$ \land ${$n$彩色可能 }
 $\lnot${$(n-1) $彩色可能 }$\Longleftrightarrow \lnot${$(n-1) $部グラフである }
 $n$彩色可能 $\Longleftrightarrow n$部グラフ
より、
 {$\lnot${$(n-1)$彩色可能}$\land${$n$彩色可能}}
$\Longleftrightarrow${$\lnot${$(n-1)$グラフ}$\land${$n$グラフ}}

 $(n-1)$部グラフでない$n$部グラフの類には準完全頂点が属している

 準完全頂点以外のそれぞれの頂点は、(必ず)隣接していない($n$部グラフの)類がある。
 $n$部グラフの類$C(x)$の元全てが準同型頂点でないと仮定すると、それらの頂点は自分の隣接していない類に移すことができるので、「$(n-1)$部グラフでない」と矛盾する。
 背理法により、準完全頂点が属している。

 $(n-1)$部グラフでない$n$部グラフにおいて、準完全頂点$v$は、隣接していない全ての類について、その類に属している準完全頂点のうち少なくとも$1$つと隣接している

 隣接している類の中に、$v$と隣接する準完全頂点が$1$つもないような類が存在すると仮定すると、その類を$C(x)$とし、$v$と隣接する$C(x)$の元を全て別の類に移すと、$v$が準完全頂点である事と矛盾する。
 背理法により題意は示された。

 $(n-1)$部グラフでない$n$部グラフは準完全$n$部グラフをマイナーとして含む

 補題$3$より準完全頂点はすべての類に"存在する"。
 ここで、準完全頂点以外の全ての頂点と、その頂点と接している辺を除く。この時、補題$4$より既存の準完全頂点は準完全頂点のままである。
 以上の動作により、準完全$n$部グラフをマイナーとして含む。

 準完全$n$部グラフにおいて、$(n-1)$つの類の位数が$1$ならば
$K_{n}$をマイナーとして含む

 位数が$1$でない類の任意の元をとると、それは準完全頂点なので、位数が$1$である全ての類の元と隣接している。また、位数が$1$である類の元同士も隣接しているので、$K_{n}$を含む。

 準完全$n$部グラフは$K_{n}$をマイナーとして含む

 位数が$1$でない類が$2$つ以上存在するとき、つまり、位数が$1$である類が$(n-1)$つ未満のとき、以下の動作で位数が$1$である類を増やせる。
\begin{eqnarray} \left\{ \begin{array}{l} 1)位数が1でない任意の類のうち1つを選ぶ(便宜上その類をC(x)とする)。 \\ 2)C(x)の任意の元のうち1つをvとする。 \\ 3)C(x)のv以外の全ての元と、位数が1でないC(x)以外の1つの類 \\ \hspace{ 10pt } (便宜上その類をC(y)とする)の元を縮約し、縮約後にできた頂点 \\ \hspace{ 10pt } らを改めてC(y)の元とする。ただし、それらの頂点はたがいに隣 \\ \hspace{ 10pt }接しているかもしれないので、その場合はさらにC(y)の元同士で \\ \hspace{ 10pt }縮約し、縮約後にできた頂点を改めてC(y)の元とし \cdots 、として \\ \hspace{ 10pt }いく(そうするとC(y)の元同士は隣接しなくなる)。\\ 4)上記の動作をすると、C(x)は位数が1になる。またC(y)の位数も \\ \hspace{ 10pt }1になる場合もあるが、もちろんそうならない場合もある。 \\ \end{array} \right. \end{eqnarray}
 この動作を繰り返すと、最終的に位数が1である類の個数は、"$(n-1)$つ"または"$n$つ"になる。
 "$(n-1)$つ"の場合、補題6より$K_{n}$をマイナーとして含む。そして、"$n$つ"の場合、それは$K_{n}$そのものである。
 上記の動作はすべてマイナーをとる動作に由来しているので、準完全$n$部グラフは$K_{n}$をマイナーとして含む。


次に、step2の証明をする。

 対偶を代わりに示す。
 最小彩色数を$n\geq5$とすると、補題$2$より、$(n-1)$部グラフでない$n$部グラフである。
 補題$5$より、準完全$n$部グラフをマイナーとして含む。
 補題$7$より、$K_{n}$をマイナーとして含む。

step3

 最小彩色数が$5$以上でないということは、最小彩色数は$4$以下である。
 最小彩色数が$4$以下ということは、$4$彩色可能である。


以上より、平面グラフは$4$彩色可能である。

前回と比べると非常に苦しい内容になってしまったかと思います。それでも、ここまで読み進めてくださった皆さん、ありがとうございました。またどこかで会いましょう。

投稿日:2023219

この記事を高評価した人

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

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

バッジはありません。

投稿者

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

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中