☆四色問題の簡単な証明その3☆
■ このスレッドは過去ログ倉庫に格納されています
0548132人目の素数さん
2013/01/08(火) 20:08:36.26>すべての彩色はすべてケンぺ鎖で表現できると仮定している。
すべての彩色は白地図から塗りなおせるので同じ事だと思うが、
3彩色可能なグラフがケンぺ鎖で表現できるのならば、
4点が4彩色のグラフもケンぺ鎖で表現できる。
5頂点の彩色数と5頂点の内で同色の2頂点の数の関係を考えると、
5頂点が5彩色ならば、5頂点の内で同色の2頂点は0組、
5頂点が4彩色ならば、5頂点の内で同色の2頂点は1組、
5頂点が3彩色ならば、5頂点の内で同色の2頂点は2組となる。
このことを踏まえると、接合を用いて5頂点が3彩色可能であること
を示すには2組の接合を行う必要がある。
しかし、2組の接合を行った後のグラフは一般に平面にはならない。
1組の接合では一般には5頂点が4彩色可能ということまでしか示せない。
上記のこととは別のことになるが、接合により彩色に5色必要に
なるかどうかは接合する2頂点および隣接する頂点の色で決まるので
ケンペ鎖の存在とは関係ない。
■ このスレッドは過去ログ倉庫に格納されています