HEXの定理(2) - フィボナッチ・フリーク

この記事は以下の記事の続きです: fibonacci-freak.hatenablog.com さて、前回はHEXの定理とBrouwerの不動点定理が実は同値であるということを紹介しました。今回はその証明を書こうと思います。それぞれのステートメントを確認しておきましょう。 定理(HEXの定理). HEXに引き分けは存在しない。すなわち全てのタイルが塗られていれば、どちらかの色は自陣をつないでいる。 定理(Brouwerの不動点定理). とすると、任意の連続写像は不動点（なる点）をもつ。 証明のための第一歩はHEXの定理の次のような言い換えです。 命題. 下図のようなグラフの頂点を赤と青の2色で塗り分ける。このとき次のいずれかが存在する。 (1)上下の辺を結ぶ道で赤い頂点からなるもの。 (2)左右の辺を結ぶ道で青い頂点からなるもの。 HEXの盤面をそのままグラフに直せば、これがHEXの定理と