大きく$3$ステップに分かれる。$\cdots$step3step1クラトフスキーの定理より、平面グラフは$K_{5}$をマイナーとして含まない。$K_{5}$をマイナーとして含まないならば$K_{n\geq5}$もマイナーとして含まない。以前投稿した記事の中で、クラトフスキーの定理を間違えて提示してしまった。"マイナー"という概念やクラトフスキーの定理については、読者諸君が各々調べてほしい。step2まずは幾つか補題を示す。$n$彩色可能$\Longleftrightarrow$$n$部グラフであるグラフ$g$を$n$彩色とすると、色の同値類が$n$個できるが、その色の同値類を$n$部グラフの類とみなすと、$n$部グラフになる。逆に、$n$部グラフの類ごとに彩色すれば$n$彩色可能である。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$である類を増やせる。1)位数が1でない任意の類のうち1つを選ぶ(便宜上その類をC(x)とする)。2)C(x)の任意の元のうち1つをvとする。らを改めてC(y)の元とする。}いく(そうするとC(y)の元同士は隣接しなくなる)。4)上記の動作をすると、C(x)は位数が1になる。}1になる場合もあるが、もちろんそうならない場合もある。\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$彩色可能である。前回と比べると非常に苦しい内容になってしまったかと思います。それでも、ここまで読み進めてくださった皆さん、ありがとうございました。どこかで会いましょう。投稿者12匁/Ichini-Momme2009年生まれです。youtubeでは音楽を、twitterでは日常や数学についての投稿をしています。幾何は詳しくないですが、代数や論理などは得意です。今後ともよろしくお願いします。高評価したユーザはいませんこの記事に送られたバッジバッジはありません。バッチを贈って投稿者を応援しようバッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。バッチを贈るコメント12匁/Ichini-Momme2009年生まれです。youtubeでは音楽を、twitterでは日常や数学についての投稿をしています。幾何は詳しくないですが、代数や論理などは得意です。今後ともよろしくお願いします。四色定理のパズル的証明(訂正版)。