離散数学 - 数学の勉強掲示板
コメントする
検索
画像一覧
2まーさん。 
2023/03/17 15:45
橋を持たない3正則グラフ $G$ に対して、まず次の補題を考えます。
補題: 橋を持たない連結グラフ $G$ に対して、$G$ が偶数個の頂点を持つ場合、$G$ には必ず2因子が存在する。
証明: 頂点数が偶数の場合、グラフ $G$ を次のように分割することができます。
$G$ の任意の1つの頂点を選び、それを含む偶数サイズのサブグラフを1つ作る。
残りの頂点を含む偶数サイズのサブグラフを複数作る。このとき、各サブグラフは $G$ の橋を含まないことに注意してください。
このような分割ができるのは、$G$ が橋を持たないことから、任意の頂点を削除してもグラフが連結であることが保証されるためです。
これらの偶数サイズのサブグラフは、それぞれ完全マッチングになっています。これは、完全マッチング定理によって示されます。従って、これらをすべて合わせることで、$G$ の2因子が得られます。
以上の補題を用いて、橋を持たない3正則グラフ $G$ について考えます。$G$ は偶数個の頂点を持ちます（頂点数が奇数の場合、次数の和が奇数になってしまうため、3正則にはなりません）。従って、先ほどの補題により、$G$ には必ず2因子が存在します。
4pt
0pt
2023/03/17 15:45
橋を持たない3正則グラフ $G$ に対して、まず次の補題を考えます。
補題: 橋を持たない連結グラフ $G$ に対して、$G$ が偶数個の頂点を持つ場合、$G$ には必ず2因子が存在する。
証明: 頂点数が偶数の場合、グラフ $G$ を次のように分割することができます。
$G$ の任意の1つの頂点を選び、それを含む偶数サイズのサブグラフを1つ作る。
残りの頂点を含む偶数サイズのサブグラフを複数作る。このとき、各サブグラフは $G$ の橋を含まないことに注意してください。
このような分割ができるのは、$G$ が橋を持たないことから、任意の頂点を削除してもグラフが連結であることが保証されるためです。
これらの偶数サイズのサブグラフは、それぞれ完全マッチングになっています。これは、完全マッチング定理によって示されます。従って、これらをすべて合わせることで、$G$ の2因子が得られます。
以上の補題を用いて、橋を持たない3正則グラフ $G$ について考えます。$G$ は偶数個の頂点を持ちます（頂点数が奇数の場合、次数の和が奇数になってしまうため、3正則にはなりません）。従って、先ほどの補題により、$G$ には必ず2因子が存在します。
4pt0pt関連トピック
掲示板TOPへ戻る