ここから本文です

3-正則グラフの頂点数|G|が偶数になる証明を教えてください。

nat********さん

2010/4/922:09:52

3-正則グラフの頂点数|G|が偶数になる証明を教えてください。

グラフ理論の教科書で、1-因子定理の説明の時に、

「3-正則グラフの頂点数は偶数になる」

との記述がありましたが、証明が載っていませんでした。
1-正則グラフでは、|G|が偶数なのは自明ですが、2-正則グラフは、偶数、奇数両方になるし、3以上だと、

Gが、n-正則グラフの時、|G|≡n+1 (mod 2)

となりそうなのですが、証明方法が思いつきません。

閲覧数:
1,810
回答数:
1
お礼:
25枚

違反報告

ベストアンサーに選ばれた回答

due********さん

編集あり2010/4/1101:16:06

グラフ理論の事は良くしらないのでまちがえてたら、ごめんなさい。
正則グラフは、単純グラフの場合も多重グラフの場合もあるとして、

「3-正則グラフの頂点数は偶数になる」
単純グラフの場合、
3-正則グラフの全辺数を出すことを考えます。
まず、1頂点にたいして、次数が全て3であり、全頂点数を|G|として、
3*|G|
を考えます。
2頂点に対して、1辺が対応しますが、上の数は2頂点に対して、
1辺をちょうど2回数えて合計した数になっているので、2で割れば全辺数がでてきます。
従って、3-正則グラフの全辺数は、
3*|G|/2
となりますが、これが、0以上の整数にならなければいけません。
つまり、3*|G|が2で割り切れると言う事です。
したがって、|G|は2で割り切れなければならない。
よって、|G|は偶数でなければならない。

多重グラフの場合、
3-正則グラフのループしていない別の頂点につながっている辺の全数をLとします。次にループしている頂点をm個とします。
ループしていない頂点は、他の頂点に向かって3つの辺がでています。ループしている頂点は1ループで辺(枝)を2回分数えますから、他の頂点に向かって、1つの辺がでています。それを考慮して、
3*(|G|-m)+1*m
と言う数を考えます。
2頂点に対して辺が数本あるとしても、上の数はその内の1つの辺をちょうど2回数えて合計した数になっているので、2で割ればLがでてきます。
従って、
{3*(|G|-m)+1*m}/2=L
となりますが、これを変形すると、
3*|G|=2*(m+L)
となります。
(m+L)は0以上の整数ですので、3*|G|が2の倍数になります。
よって、|G|は偶数でなければならない。

で、如何でしょうか?

この理屈が正しいなら、5-正則グラフの場合1ループする頂点の個数をm(1)、2ループする頂点の個数をm(2)とすると、
同様に、
{5*(|G|-m(1)-m(2))+3*m(1)+1*m(2)}/2=L
5*|G|=2*(m(1)+2*m(2)+L)
となり、やはり、|G|は偶数でなければならない。
同様に考えれば、nが奇数ならn-正則グラフの、
|G|は偶数になる事は言えると思います。

質問した人からのコメント

2010/4/13 06:49:16

抱きしめる 多重グラフまで考えていただき、ありがとうございます。 偶数次の正則グラフの頂点数が奇数になると誤解していたことことが、問題の本質を見誤っていた様です。

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる