正則2部グラフ

正則2部グラフ

空でない正則2部グラフの2分割を(X,Y)とすると、XとYは同じ大きさであることを示せ。

という問題です。

2部グラフ…頂点集合が互いに素な部分集合XとYに分けられ、各辺の両端点は一方がXに、他方がYに含まれるグラフ

正則グラフ…すべての頂点の次数が等しいグラフ

この定義は理解しています。ただ、問題が自明な感じがして証明が思いつきません。
どなたか証明法を教えてください。

No.3 ベストアンサー 回答者： boiseweb 回答日時： 2010/07/02 22:54

No.1回答者です．

>「2部グラフにおいて」、頂点集合を二つの部分集合に、各集合内の頂点同士の間には辺が無いように分けること、と思っています。

その定義であれば，あとは，各集合に属する頂点の次数の総和を議論すれば終わりでしょう．

ところで，私は，グラフ理論で「2分割」という語を上記の意味に使うことが信じられません．質問者さんが問題文を誤読しているのでなければ，出題者の用語の使い方が無茶苦茶だと思います．私なら，「2分割」の定義が特段に明示されていなければ，「（任意の）グラフの頂点集合を2つの（空でない）部分集合に分けること」と解釈し，ご質問の問題は当然に「偽」と判断します．

ついでに言うと，「空でない正則2部グラフ」というのも，あいまいさがあります．Wikipediaによると「空グラフ」は「頂点も辺もないグラフ」「辺がないグラフ」の2つの解釈があるようで，ご質問の問題の「空でない」は後者の解釈で考える必要があります．

この回答へのお礼

ご回答ありがとうございます。

お礼日時：2010/07/03 09:35

No.2 回答者： alice_44 回答日時： 2010/07/02 22:41

X の頂点数を x、

Y の頂点数を y、
正則グラフの次数を n とすると、

X に接続する辺の総数が nx、
Y に接続する辺の総数が ny となって、
両者は等しい。

すなわち、nx = ny より
x = y。

この回答へのお礼

ご回答ありがとうございます。

お礼日時：2010/07/03 09:35

No.1 回答者： boiseweb 回答日時： 2010/07/02 21:54

質問者さんの理解に基づく「2分割」の定義を補足にどうぞ．

2分割とは，一般のグラフについて定義できるのか，正則グラフについてのみ定義できるのか，2部グラフについてのみ定義できるのか，それも含めて．

この回答への補足

「2部グラフにおいて」、頂点集合を二つの部分集合に、各集合内の頂点同士の間には辺が無いように分けること、と思っています。

補足日時：2010/07/02 22:03