五色定理
そこで、頂点 v 1 {\displaystyle v_{1}} , v 2 {\displaystyle v_{2}} , v 3 {\displaystyle v_{3}} , v 4 {\displaystyle v_{4}} , v 5 {\displaystyle v_{5}} はそれぞれ色 1, 2, 3, 4, 5 で塗られていると仮定する。
グラフ G ′ {\displaystyle G'} から、色1または3で塗られた頂点と、それらを接続する辺だけを取り出した部分グラフ G 1 , 3 {\displaystyle G_{1,3}} を考える。明らかにどの辺も色1の頂点と色3の頂点を結ぶ(これをケンプ鎖(英語版)という)。もし v 1 {\displaystyle v_{1}} と v 3 {\displaystyle v_{3}} とがグラフ G 1 , 3 {\displaystyle G_{1,3}} の異なる連結成分に属するならば、 v 1 {\displaystyle v_{1}} が属す連結成分で色1と色3を交換することで、頂点 v {\displaystyle v} を色1で塗ることができるようになり、証明が終わる。
そうでない場合、 v 1 {\displaystyle v_{1}} と v 3 {\displaystyle v_{3}} とはグラフの同一の連結成分に属すことになるので、色1と色3の頂点のみを伝ってこれらを結ぶ G 1 , 3 {\displaystyle G_{1,3}} の道を見つけることができる。