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

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

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

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

　対偶を示す。("$s-1$部グラフでない$s$部グラフ"を含まない$\Longrightarrow$"$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$のグラフは必ず$K_{n}$を含む__と言い換えられる(同値である)。

　ここで、補題1より、"最小彩色数が$n$である$ \Longleftrightarrow$$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}$と完全に結ばれていないと仮定すると$ \cdots (*)$、$v$と結ばれていない$K_{k}$の頂点を同じ同値類に入れることができるため、$k$部グラフになってしまい矛盾する。
　よって仮定$(*)$が間違っていることとなり、$K_{k}$と完全に結ばれている$v \in C(v)$が存在することがわかる。そして$ \exists v \in C(v)$と$K_{k}$を完全に結んだグラフは$K_{k+1}$である。

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