2因子定理

グラフ理論という数学の 分野において、ジュリアス・ピーターセンによって発見された2因子定理は、グラフ理論における最も初期の研究の一つである。それは次のように述べられる: ^[1]

を次数が偶数である正則グラフとします。このとき、 の辺は辺が互いに素な 2 因子 に分割できます。${\displaystyle G}$${\displaystyle 2k}$${\displaystyle G}$${\displaystyle k}$

ここで、2 因子は、すべての頂点が次数 2 である のサブグラフです。つまり、各頂点に 1 回だけ接触するサイクルの集合です。 ${\displaystyle G}$

この定理の一般化された形を証明するために、ピーターセンはまず、4-正則グラフがオイラー経路で交互の辺を取ることによって2つの2-因数に因数分解できることを証明した。彼は、4-正則グラフに使用されたのと同じ手法で、-正則グラフを2つの-因数に因数分解できることを指摘した。^[2]${\displaystyle 2k}$${\displaystyle k}$

この定理を証明するには、連結グラフを考えれば十分です。偶数次数の連結グラフにはオイラートレイルがあります。このオイラートレイルをたどると、すべての点が入次数 と出次数 を持つようなの向き が生成されます。次に、すべての頂点を2 つの頂点と に置き換え、有向グラフのすべての有向辺を から への無向辺に置き換えます。の入次数と出次数は に等しいため、結果として得られる二部グラフは-正則です。 の辺は、ケーニヒ の定理によって完全マッチングに分割できます。次に、すべての についてを と併合するとグラフ が復元され、の完全マッチングがの辺を分割するの 2 因子にマッピングされます。^[1]${\displaystyle D}$${\displaystyle G}$${\displaystyle =k}$${\displaystyle v\in V(D)}$${\displaystyle v'}$${\displaystyle v''}$${\displaystyle uv}$${\displaystyle u'}$${\displaystyle v''}$${\displaystyle D}$${\displaystyle k}$ ${\displaystyle G'}$${\displaystyle k}$${\displaystyle G'}$${\displaystyle k}$${\displaystyle v'}$${\displaystyle v''}$${\displaystyle v}$${\displaystyle G}$${\displaystyle k}$${\displaystyle G'}$${\displaystyle k}$${\displaystyle G}$

この定理はデンマークの数学者ジュリアス・ペーターセンによって発見された。これはグラフ理論の分野で初めて発見された結果の一つである。この定理は1891年の論文「規則グラフの理論」に初めて登場する。この定理を証明するために、ペーターセンはトレイルやパスの端を交互に赤と青に「色付け」し、片方または両方の色の端を他のパスやトライの構築に使用するという基本的なアイデアを考案した。^[3]

• ピーターセンの定理– すべての3正則なブリッジレスグラフには2因子が含まれる