-PR-
解決済み

グラフ理論の問題

  • 困ってます
  • 質問No.95057
  • 閲覧数252
  • ありがとう数1
  • 気になる数0
  • 回答数1
  • コメント数0

お礼率 85% (6/7)

この問題がどうしても解けません。
(a) どんな単純グラフにも次数が同じ点が2個以上あることを示せ。
どうかお願いいたします。
通報する
  • 回答数1
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.1
レベル8

ベストアンサー率 33% (10/30)

帰納法を使います。

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

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

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

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

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


もうちょっとうまいやり方がありそうなものですが、
ちと思い付きませんでした。
お礼コメント
akirasuzu

お礼率 85% (6/7)

ありがとうございました。おかげさまで後の問題もすんなり解くことができました。
投稿日時 - 2001-07-01 21:41:23
-PR-
-PR-
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


新大学生・新社会人のパソコンの悩みを解決!

いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ