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

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

　グラフ$g$を$n$彩色とすると、色の同値類が$n$個できるが、その色の同値類を$n$部グラフの類とみなすと、$n$部グラフになる。
　逆に、$n$部グラフの類ごとに彩色すれば$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$部グラフの)類がある。
　$n$部グラフの類$C(x)$の元全てが準同型頂点でないと仮定すると、それらの頂点は自分の隣接していない類に移すことができるので、「$(n-1)$部グラフでない」と矛盾する。
　背理法により、準完全頂点が属している。

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

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

　位数が$1$でない類の任意の元をとると、それは準完全頂点なので、位数が$1$である全ての類の元と隣接している。また、位数が$1$である類の元同士も隣接しているので、$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}$をマイナーとして含む。

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

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