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

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

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

　最小彩色数が$n⟺\mathrm{\neg }${$(n-1)$彩色可能 }$\wedge${$n$彩色可能 }
　$\mathrm{\neg }${$(n-1)$彩色可能 }$⟺\mathrm{\neg }${$(n-1)$部グラフである }
　$n$彩色可能 $⟺n$部グラフ
より、
　{$\mathrm{\neg }${$(n-1)$彩色可能}$\wedge${$n$彩色可能}}
$⟺${$\mathrm{\neg }${$(n-1)$グラフ}$\wedge${$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{array}{r}\{\begin{array}{l}1)位数が1でない任意の類のうち1つを選ぶ(便宜上その類をC(x)とする)。\\ 2)C(x)の任意の元のうち1つをvとする。\\ 3)C(x)のv以外の全ての元と、位数が1でないC(x)以外の1つの類\\ (便宜上その類をC(y)とする)の元を縮約し、縮約後にできた頂点\\ らを改めてC(y)の元とする。ただし、それらの頂点はたがいに隣\\ 接しているかもしれないので、その場合はさらにC(y)の元同士で\\ 縮約し、縮約後にできた頂点を改めてC(y)の元とし\cdots 、として\\ いく(そうするとC(y)の元同士は隣接しなくなる)。\\ 4)上記の動作をすると、C(x)は位数が1になる。またC(y)の位数も\\ 1になる場合もあるが、もちろんそうならない場合もある。\end{array}\end{array}$$
　この動作を繰り返すと、最終的に位数が1である類の個数は、"$(n-1)$つ"または"$n$つ"になる。
　"$(n-1)$つ"の場合、補題6より$K_n$をマイナーとして含む。そして、"$n$つ"の場合、それは$K_n$そのものである。
　上記の動作はすべてマイナーをとる動作に由来しているので、準完全$n$部グラフは$K_n$をマイナーとして含む。

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

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