ピーターセンの定理

数学におけるピーターセンの定理（ピーターセンのていり、）はグラフ理論の最初期の結果の一つで、名称は数学者ジュリウス・ピーターセンに由来し、以下を主張する。
言い換えると、もしグラフの全ての頂点がちょうど3本の辺で接続されていて、全ての辺がいずれかの閉路の一部であるならば、どの2つも隣接しないようなグラフの辺集合を上手く選んで、それらの端点を集めたものがグラフの頂点全体と一致するようにできる。
証明.
 を任意の橋のない立方体グラフとする。任意の頂点部分集合 に対し、 が誘導する部分グラフの奇数個の頂点を持つ連結成分の個数 が 以下であることを示せば、タットの定理から が完全マッチングを持つことがわかる。
そこでそのような連結成分を一つ任意にとって とする。 の頂点集合を 、両端が に属すような の辺の総数を 、端点の一方が に属し、もう一方が に属すような の辺の総数を とする。 全体にわたる頂点の次数の和を2通りに数え上げることで、次の等式が得られる。 
中辺は奇数で は偶数なので は奇数でなければならず、さらに は橋を持たないので である。
端点の一方が に属し、もう一方が に属すような の辺の総数を とする。 の奇頂点連結成分1つにつき、この条件を満たす辺は3個以上あり、かつ異なる連結成分間での重複はない。よって 。一方で の全ての頂点の次数は3だから 。これらをあわせて
ゆえにタットの定理の前提条件が満たされ、ピーターセンの定理は証明された。
歴史.
この定理はデンマークの数学者ジュリウス・ピーターセンに負う。グラフ理論における最初期の結果の一つと考えられる。定理が初めて世に出たのは1891年の論文 "Die Theorie der regulären graphs" においてであった。今日的な基準からすると、ピーターセンの証明は非常に入り組んだものだった。、次いでは、ピーターセンの定理の証明を劇的に簡潔化した。
現代の教科書ではピーターセンの定理はタットの定理の一応用例とされる。
拡張.
完全マッチングの数.
ラースロー・ロヴァースとは、橋のない立方体グラフの完全マッチングの数は、頂点数 の指数関数的に増大すると予想した。この予想はまず2部グラフの場合に証明され()、次いで平面グラフの場合に証明された(、受付は2009年)。一般の橋のない立方体グラフの場合、少なくとも formula_3 の完全マッチングが存在することが示されている(、受付は2010年)。
より高い次数の場合.
"d" 次の正則グラフ "G" の辺連結度が "d" − 1 以上で、かつ "G" の頂点数が偶数であれば、完全マッチングが存在する。このときさらに、"G" の任意の辺に対しそれを含むような完全マッチングが存在することが言える（なお次数 "d" が奇数のときは （handshaking lemma）より頂点数は必ず偶数になるから、これを仮定する必要はなくなる）。