質問: 3-正則グラフの頂点数|G|が偶数になる証明を教えてください。
回答: グラフ理論の事は良くしらないのでまちがえてたら、ごめんなさい。 正則グラフは、単純グラフの場合も多重グラフの場合もあるとして、 「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|は偶数になる事は言えると思います。