グラフ理論の問題

質問

この問題がどうしても解けません。
（a）　どんな単純グラフにも次数が同じ点が２個以上あることを示せ。
どうかお願いいたします。

回答No.1

nagata · ベストアンサー

帰納法を使います。

頂点数が2の時(a)は成り立つ。
頂点数が2以上k以下の時(a)が成り立つと仮定すると、
頂点数がk+1の時、

1)グラフに辺が一本も無いとき、明らか。

2)グラフが非連結で辺が一本以上あるとき、
このグラフは頂点数2以上k以下の連結成分を持つ。
この連結成分は帰納法の仮定より同じ次数の頂点を持つ。
よってこのグラフも同じ次数の頂点を持つ。

3)グラフが連結であるとき、
各頂点の次数は1以上k以下のk種類である。頂点はk+1個あるので
鳩の巣原理より、同じ次数の頂点が存在する。

以上より(a)は成り立つ。

もうちょっとうまいやり方がありそうなものですが、
ちと思い付きませんでした。

お礼

ありがとうございました。おかげさまで後の問題もすんなり解くことができました。