torlyの日記: よーしパパ隣接しちゃうぞー 2
日記 by
torly
点集合AとBがあり、同じ集合に属する点同士は辺で結ばれていないものとする。木の全ての点をAかBに振り分けられるなら、木は二部グラフであると言える。
ある点v1∈A、v2と隣接する点v2∈Bとする。木の辺は全て橋なので、閉路は存在しない。故に、v2と隣接している点はv1とは隣接していない。よって、それらは全てAに入れる事が出来る。v1と隣接している点についても同様に、v2と隣接していないので、全てBに入れる事が出来る。これを繰り返せば、全ての点をAかBに入れる事が可能である。よって、木は二部グラフである。
ある点v1∈A、v2と隣接する点v2∈Bとする。木の辺は全て橋なので、閉路は存在しない。故に、v2と隣接している点はv1とは隣接していない。よって、それらは全てAに入れる事が出来る。v1と隣接している点についても同様に、v2と隣接していないので、全てBに入れる事が出来る。これを繰り返せば、全ての点をAかBに入れる事が可能である。よって、木は二部グラフである。
これで合ってるかなあ…
この証明って (スコア:1)
そんなものを"木"と呼ぶかは知りませんが。
非可算無限個の場合はZornの補題でも使えばよろしいかと。
ケーニッヒ (スコア:0)