ピーターセンの定理
ラースロー・ロヴァースとマイケル・D・プラマー(英語版)は、橋のない立方体グラフの完全マッチングの数は、頂点数 n の指数関数的に増大すると予想した。この予想はまず2部グラフの場合に証明され(Voorhoeve (1979))、次いで平面グラフの場合に証明された(Chudnovsky & Seymour (2012)、受付は2009年)。一般の橋のない立方体グラフの場合、少なくとも 2 n / 3656 {\displaystyle 2^{n/3656}} の完全マッチングが存在することが示されている(Esperet et al. (2011)、受付は2010年)。
この定理はデンマークの数学者ジュリウス・ピーターセンに負う。グラフ理論における最初期の結果の一つと考えられる。定理が初めて世に出たのは1891年の論文 "Die Theorie der regulären graphs" においてであった。今日的な基準からすると、ピーターセンの証明は非常に入り組んだものだった。Frink (1926)、次いでKönig (1936)は、ピーターセンの定理の証明を劇的に簡潔化した。
現代の教科書ではピーターセンの定理はタットの定理の一応用例とされる。