ピーターセンの定理

グラフ理論という数学の分野において、ジュリアス・ピーターセンにちなんで名付けられたピーターセンの定理は、グラフ理論における最も初期の結果の 1 つであり、次のように述べることができます。

ピーターセンの定理。すべての3次橋なしグラフには完全に一致するグラフが含まれる。^[1]

言い換えると、グラフの各頂点に正確に 3 つのエッジがあり、すべてのエッジがサイクルに属している場合、すべての頂点に正確に 1 回接するエッジのセットが存在します。

あらゆる立方体の橋なしグラフG = ( V , E )に対して、あらゆる集合U ⊆ Vに対して、 V  −  Uによって誘導される奇数の頂点を持つグラフの連結成分の数は、最大でUの濃度になることを示します。すると、Tutte の定理により、 Gには完全マッチングが含まれます。

G _{i を、}頂点集合V  −  Uによって誘導されるグラフの、奇数個の頂点を持つ成分とする。V _{i は}G _iの頂点を表し、m _{i は}V _iに1つの頂点、 Uに1つの頂点を持つGの辺の数を表すものとする。単純な二重カウントの議論により、次の式が得られる。

${\displaystyle \sum \nolimits _{v\in V_{i}}\deg _{G}(v)=2|E_{i}|+m_{i},}$

ここでE _{i は}G _iの辺の集合であり、その辺の頂点は両方ともV _iにある。

${\displaystyle \sum \nolimits _{v\in V_{i}}\deg _{G}(v)=3|V_{i}|}$

が奇数で2| E _i |が偶数の場合、m _{i は}奇数でなければなりません。さらに、Gはブリッジレスなので、 m _i  ≥ 3となります。

m を、Uに 1 つの頂点を持ち、 V  −  Uによって誘導されるグラフに 1 つの頂点を持つGの辺の数とします。奇数の頂点を持つすべてのコンポーネントは、 mに少なくとも 3 つの辺を提供し、これらは一意であるため、そのようなコンポーネントの数は最大でm /3です。最悪の場合、Uに 1 つの頂点を持つすべての辺がmに提供され、したがってm  ≤ 3| U |となります。

${\displaystyle |U|\geq {\frac {1}{3}}m\geq |\{{\text{components with an odd number of vertices}}\}|,}$

これはTutte 定理の条件が成り立つことを示しています。

この定理はデンマークの数学者、ユリウス・ペーターセンによるものです。グラフ理論における最初の成果の1つとみなすことができます。この定理は、1891年の論文「規則グラフの理論」に初めて登場しました。^[1]今日の基準では、ペーターセンの定理の証明は複雑です。証明の一連の簡略化は、フリンク（1926年）とケーニッヒ（1936年）による証明で最高潮に達しました。

現代の教科書では、ピーターセンの定理はタッテの定理の応用として扱われています。

• 完全マッチングを持つ立方グラフでは、完全マッチングに含まれない辺は2因子を形成します。2因子を方向付けることにより、例えば外向きの辺を取ることで、完全マッチングの辺を長さ3のパスまで拡張することができます。これは、すべての立方体の橋のないグラフが長さ3の辺が互いに素なパスに分解されることを示しています。^[2]
• ピーターセンの定理は、あらゆる極大平面グラフが長さ 3 の辺が互いに素なパスの集合に分解できることも示すために適用できる。この場合、双対グラフは立方体でブリッジがないため、ピーターセンの定理によりマッチングが成立し、これは元のグラフでは隣接する三角形の面のペアリングに対応する。三角形の各ペアは、三角形同士を接続する辺と、残りの 4 つの三角形の辺のうち 2 つを含む長さ 3 のパスを与える。^[3]
• ピーターセンの定理を三角形メッシュの双対グラフに適用し、一致しない三角形のペアを接続すると、メッシュを三角形の周期的なストリップに分解できます。さらにいくつかの変換を行うと、単一のストリップに変換できるため、三角形メッシュの双対グラフがハミルトンになるように変換する方法が得られます。^[4]

LovászとPlummerは、立方体でブリッジのないグラフに含まれる完全マッチングの数は、グラフの頂点数nの指数関数的であると予想しました。^[5]この予想は、最初にVoorhoeve (1979) によって二部立方体でブリッジのないグラフ に対して証明され、その後 Chudnovsky と Seymour (2012) によって平面でブリッジのないグラフに対して証明されました。一般的なケースは Esperet ら (2011) によって解決され、すべての立方体でブリッジのないグラフには少なくとも 1 つ以上の完全マッチングが含まれていることが示されました。 ${\displaystyle 2^{n/3656}}$

Biedl ら (2001) は、ピーターセンの定理の効率的なバージョンについて議論しています。Frink の証明^[6]に基づいて、彼らはn頂点を持つ立方体のブリッジのないグラフで完全マッチングを計算するためのO ( n log ⁴ n )アルゴリズムを得ています。グラフがさらに平面である場合、同じ論文ではO ( n )アルゴリズムも示しています。彼らのO ( n log ⁴ n )の時間制限は、動的グラフでブリッジのセットを維持するための時間に対するその後の改善に基づいて改善できます。^[7] Diks と Stanczyk (2010) は、時間制限をO ( n log ² n )または (追加のランダム化データ構造を使用) O ( n log n (log log n ) ³ )に短縮するさらなる改善を示しました。

G が次数dの正則グラフで、辺の接続性が少なくともd  − 1 であり、Gの頂点数が偶数である場合、G は完全マッチングを持つ。より強い言い方をすれば、 Gのすべての辺は少なくとも 1 つの完全マッチングに属する。次数が奇数の場合、頂点数に関する条件はこの結果から省略できる。なぜなら、その場合 (握手補題により) 頂点数は常に偶数だからである。^[8]

• 2因子定理– ピーターセンの関連定理