ざっくり言うと
間取り図に五角形の部屋があれば、外部にドアを一つも増やさずに、チョークの線を引いてそれを二つの三角形の部屋に分けることが常にできる——増えるのは内部の壁(辺)一本と、部屋(面)一つだけである。三角形でないすべての面についてこれを行っても、累計 は決して変わらない。新しい辺一本と新しい面一つが互いに打ち消し合うからである。
平面グラフのある面が四辺以上を持つ場合、それを二つの小さな面に分割する対角線を一本引く。これにより頂点にはまったく触れずに新しい辺一本と新しい面一つがちょうど加わるので、 は 増え、 も 増え、 はそのまま変わらない。これを三角形でないすべての面——四辺以上の多角形であれば必ず可能——について繰り返すと、 を一度も変えることなく、グラフ全体が三角形分割になる。
- 三角形分割
- 新しい頂点を加えることなく、対角線を引いて平面グラフのすべての面を三角形に分割する方法のこと。