ピーターセンの定理
数学におけるピーターセンの定理(ピーターセンのていり、英: Petersen's theorem)はグラフ理論の最初期の結果の一つで、名称は数学者ジュリウス・ピーターセンに由来し、以下を主張する。
定理: 橋(英語版)のない立方体グラフは、必ず完全マッチングを持つ。
言い換えると、もしグラフの全ての頂点がちょうど3本の辺で接続されていて、全ての辺がいずれかの閉路の一部であるならば、どの2つも隣接しないようなグラフの辺集合を上手く選んで、それらの端点を集めたものがグラフの頂点全体と一致するようにできる。
d 次の正則グラフ G の辺連結度が d − 1 以上で、かつ G の頂点数が偶数であれば、完全マッチングが存在する。このときさらに、G の任意の辺に対しそれを含むような完全マッチングが存在することが言える(なお次数 d が奇数のときは握手補題(英語版) (handshaking lemma)より頂点数は必ず偶数になるから、これを仮定する必要はなくなる)。
橋のない立方体グラフと、その完全マッチングを一つとる。マッチングに属さない辺集合は "2-factor" (元のグラフと頂点全体が一致するような 2-正則グラフ)を成す。この各連結成分(閉路)に向き付け(英語版)をすると、マッチングの各辺は長さ3の道に延長できる(例えば、各辺の端点に順方向の辺を加えればよい)。よって、任意の橋のない立方体グラフはどの2つも辺を共有しない長さ3の道の集合に分解できる。
ピーターセンの定理を使うと、任意の極大平面グラフ(どの2頂点を追加的に接続しても平面性が失われるような単純平面グラフ)が、どの2つも辺を共有しない長さ3の道の集合に分解できることも証明できる。
この場合は双対グラフが橋のない立方体グラフになり、ピーターセンの定理より完全マッチングがとれる。マッチングに属さない辺の閉路集合の向き付けを上手く行って、最初の例と同様にマッチングの各辺の両端に向きのついた辺を継いで長さ3の道を作ると、元のグラフでこの道に対応するのが隣接する三角形の5本の辺 "〼" を "Z" 型に通る長さ3の道(中間の辺が三角形の共有辺)になる。
ピーターセンの定理を三角メッシュ(triangle mesh)の双対グラフに適用し、マッチングに属さない隣接三角形をつないでいくと、三角メッシュをトライアングルストリップ(triangle strip)の輪の集合に分解できる。元の三角メッシュにさらにいくらかの変形(頂点と辺の追加)を施すことで、1本のトライアングルストリップにすることができる。これは双対グラフがハミルトングラフになるように三角メッシュを変形する手法を与える。