最新閲覧日:

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

A 回答 (1件)

帰納法を使います。



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

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

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

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

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


もうちょっとうまいやり方がありそうなものですが、
ちと思い付きませんでした。
    • good
    • 0
この回答へのお礼

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

お礼日時:2001/07/01 21:41

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ