ピーターセンの定理

ウィキペディア

ピーターセンの定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/20 05:15 UTC 版)

ピーターセングラフでの完全マッチング（赤色の辺集合）。ピーターセングラフは橋のない立方体グラフであり、ピーターセンの定理の仮定を満たす。

完全マッチングを持たない（橋が存在する）立方体グラフの例。「橋なし」の条件がピーターセンの定理から落とせないことを示す。

数学におけるピーターセンの定理（ピーターセンのていり、英: Petersen's theorem）はグラフ理論の最初期の結果の一つで、名称は数学者ジュリウス・ピーターセンに由来し、以下を主張する。

定理： 橋のない立方体グラフは、必ず完全マッチングを持つ。

言い換えると、もしグラフの全ての頂点がちょうど3本の辺で接続されていて、全ての辺がいずれかの閉路の一部であるならば、どの2つも隣接しないようなグラフの辺集合を上手く選んで、それらの端点を集めたものがグラフの頂点全体と一致するようにできる。

証明

G = (V, E) を任意の橋のない立方体グラフとする。任意の頂点部分集合 U ⊆ V に対し、V − U が誘導する部分グラフの奇数個の頂点を持つ連結成分の個数 o(V − U) が |U| 以下であることを示せば、タットの定理から G が完全マッチングを持つことがわかる。

そこでそのような連結成分を一つ任意にとって G_i とする。G_i の頂点集合を V_i 、両端が G_i に属すような G の辺の総数を M_i 、端点の一方が V_i に属し、もう一方が U に属すような G の辺の総数を m_i とする。V_i 全体にわたる頂点の次数の和を2通りに数え上げることで、次の等式が得られる。

$\sum \nolimits _{v\in V_{i}}\deg _{G}(v)=3|V_{i}|=2M_{i}+m_{i}$ この項目は、組合せ数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。