五色定理
ここで今度は、グラフ G ′ {\displaystyle G'} から色2または4で塗られた頂点とそれらを接続する辺だけを取り出した部分グラフ G 2 , 4 {\displaystyle G_{2,4}} に目を向け、同じ議論を繰り返すことにする。すると、グラフ G 2 , 4 {\displaystyle G_{2,4}} の v 2 {\displaystyle v_{2}} を含む連結成分において色2と色4を交換することで頂点 v {\displaystyle v} が色2で塗れるようになるか、色2と色4の頂点のみを伝って v 2 {\displaystyle v_{2}} と v 4 {\displaystyle v_{4}} を結ぶ G 2 , 4 {\displaystyle G_{2,4}} の道を見つけることができるかの、二つに一つである。ところが後者はあり得ない。なぜならそのような道は、既に見出した「色1と色3の頂点のみを伝って v 1 {\displaystyle v_{1}} と v 3 {\displaystyle v_{3}} を結ぶ道」とどこかで交わらざるを得ないからである。
以上でグラフ G {\displaystyle G} が5色で塗り分けられることが判明した。