「木は２部グラフである。」を証明して下さい！

質問

「木は２部グラフである。」
これを証明して欲しいのです。
出来れば背理法で。
よろしくお願いします。

回答No.2

stomachman · ベストアンサー

お気に召さない？
自明すぎて困っちゃうんですが、そうだな、木のノードが奇数番目と偶数番目に分けられる。つまりノードに赤と青の色を付けて、どの辺も一端が赤、他端が青のノードを繋ぐようにできる。

どれでも良いから一つノードを選んで赤にする。
これに辺１本で繋がっている全てのノードを青にする。
青のノードに辺１本で繋がっている全てのノードを赤にする。

これを繰り返せば、木は連結しているから全てのノードに色が付きます。
次に、木はループがないから、一度赤がついたノードは何度色を塗っても赤ですし、青がついたノードは青。

これなら証明っぽいですか？

回答No.1

stomachman

２部グラフ：ノードを二つの部分集合A,Bに分けて、どの辺も一端をAに他端をBに持つようにできること。

木が２部グラフであることは、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明。

背理法？
木が２部グラフでないとすると、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明であることと矛盾する。QED