だったらこれならどう？

隣合う2頂点とそれを囲むサイクルを考える。
このサイクルが4彩色されている場合、この2頂点を縮約すると5色目が必要になる。
これはN-1のグラフが4彩色可能であるという仮定に反するので、隣合う2頂点を囲むサイクルは
高々3彩色であることがわかる。
3彩色のサイクルに囲まれる2頂点は、残る1色を割り当てた1頂点に縮約することができる。
以上より、隣合う2頂点は可約であることが証明できた。