第2部:
(c) が成り立たない, すなわち
(d) G_1 の任意の4配色は p1〜p5 を塗るのに4色を用いる
と仮定し, 矛盾を導く。

言葉をひとつ用意する。
グラフ G_1 の4配色がひとつ与えられたとき, A色で塗られていた
頂点をB色で, B色で塗られていた頂点をA色で塗り替えても、
やはり G1 の4配色になる。
このようにグラフG_1 の4配色 f_1 と f_2 があったとき、
f_1 のA,B,C,D を入れ替えて f_2 が得られるなら、f_1 と f_2 は
「同値な4配色」と呼ぶ。

(d) は次と同値である:
(e) G_1 の任意の4配色 f に対して, それと同値な4配色で p1〜p5
　　を塗るのに4色を使い, さらにB色を2回用い, ACチェーンと
　　ADチェーンがつながっているものが存在する

実際 (e) ならば (d) は明らか。
(e) が成り立たなければ, Kempe の手法に従えば, p1〜p5 を3色以下
で塗る方法が得られる。すなわち (d) が成り立たない。対偶をとれば
(d) ならば (e) が示された。

なお「ACチェーンがつながっている」とは, 例えば p1 が A色, p3が
D色で塗られているとき, p1 から出発して A--> D--> A--> D のように
頂点を辿っていって p3 に到達できることをいう