五色定理
まず、与えられた地図に単純な平面グラフ G {\displaystyle G} を対応させる。つまり、地図の各領域をグラフの頂点とし、2領域が隣接しているときかつそのときに限り、対応する2頂点を1つの辺で結ぶものとする。こうして問題はグラフの彩色問題に変換される:各頂点に色を塗って、どの辺についても端点である2頂点の色が一致しないようにできるか。
グラフ G {\displaystyle G} は単純平面グラフである、つまり平面上にどの2辺も交差させることなく描くことができ、かつどの2頂点間にも2本以上の辺が存在せず、ループも存在しないので、平面のオイラー標数を用いることで、グラフ G {\displaystyle G} には最大でも5本の辺によってしか接続されていないような頂点が存在することが証明できる(注意:五色定理の仮定(色の数が最大で5)が使われるのはこの箇所だけである。もし同じ手法で四色定理を証明しようとしても、この段階で頓挫する。実際、正二十面体グラフ(icosahedral graph)は5-正則な平面グラフであり、接続する辺が4本以下であるような頂点は存在しない)。このような頂点を1つ選んで v {\displaystyle v} と呼ぶことにする。
今、頂点 v {\displaystyle v} を G {\displaystyle G} から取り除く。