正則2部グラフ

質問

正則2部グラフ

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

という問題です。

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

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

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

回答No.3

boiseweb · ベストアンサー

No.1回答者です．

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

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

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

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

お礼

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

回答No.2

alice_44

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

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

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

お礼

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

回答No.1

boiseweb

質問者さんの理解に基づく「2分割」の定義を補足にどうぞ．
2分割とは，一般のグラフについて定義できるのか，正則グラフについてのみ定義できるのか，2部グラフについてのみ定義できるのか，それも含めて．

補足

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