●問題1

定理：ある平面的グラフは5-彩色可能である。

グラフの頂点の個数pに関する帰納法による。p≦5のとき,定理は成立する。

『p≦5のとき,定理は成立する』の理由を説明しなさい。

●問題2

p>5で,p-1個以下の頂点を持つグラフに対して,定理が成り立つとする。
問題1により,グラフは次数が5以下の頂点を持つ。帰納法の定理により,グラフ-vは5-彩色可能である。
よってグラフ-vは5-彩色されていると仮定する。vに隣接している頂点が,4色以下で彩色されているならば,
vに残った一色で彩色すれば,5-彩色グラフが得られる。vが彩色された頂点と隣接している場合を考えればよい。
それらの頂点を,v1,v2,v5と呼ぶ。また,各頂点の色をc1,c2, ... ,c5とする。

c1とc3で彩色される頂点で形成されたグラフを部分グラフＫとする。Ｋはv1,v3を含む。
v1とv3がＫの異なる部分グラフに含まれているときは,v1が含まれている部分グラフの頂点に彩色
されている。c1,c3をグラフ-vの他の頂点の色を変更せずとも,そっくり並べ替えることができる。
このとき,v1,v3がc3で塗られ,ｖをc1で塗ることができる。よって,グラフの5-彩色ができる。

上の文章には,
『v1とv3がＫの異なる部分グラフに含まれているときは,v1が含まれている部分グラフの頂点に彩色
されている。c1,c3をグラフ-vの他の頂点の色を変更せずとも,そっくり並べ替えることができる。』とある。

なぜ,c1,c3をそっくり入れ替えることができるのか？理由を述べなさい。


おねがいします　っm