グラフの問題です。 ２n頂点のグラフGがあり、その頂点をA_1,B_1,,A_2,B_2,,,,A_

グラフの問題です。
２n頂点のグラフGがあり、その頂点をA_1,B_1,,A_2,B_2,,,,A_nB_nとする。全てのiに対して、A_iB_i∉E(G)であり、頂点A_1以外のすべての次数は異なっている。
この時、頂点B_1の次数を求めよ。
という問題なんですが、具体的なn=３のときは、6頂点でどの頂点も非隣接な頂点があることから、A_1以外の頂点の次数は0,1,2,3,4となり、最大次数をB__2にすると自然にA_2の次数は0というように順々に決定していけるのですが、頂点の次数が2nだとどのようにしていけば良いかわからないです。ややこしいのですが、どなたか解説のほうお願いします。

質問者からの補足コメント

• 回答ありがとうございます。
  n＝4やりました。
  b_1の頂点は3となりました。
  n＝5の時もやり、
  b_1の頂点は4でした。
  n＝3の時は、2
  n＝4の時は、3
  n＝5の時は、4と規則性でおそらくn＝kのときは、
  b_1＝k−1だと思うのですが、3.4.5が規則に沿っているだけで、それ以降は規則通りなっているかどうかはどのようにしていけば良いのでしょうか？

    補足日時：2017/07/18 00:12

• 帰納法での証明のやり方
  教えてもらえないですか？

    補足日時：2017/07/18 00:42

• 帰納段階のやり方出来なさそうですか？

    補足日時：2017/07/19 02:15

No.4 ベストアンサー 回答者： Tacosan 回答日時： 2017/07/19 11:22

「帰納段階のやり方出来なさそうですか？」というのは, いったい何を意図した質問なのでしょうか.

ひょっとして, 私が何かを書くのを待っていたのですか? もしそうだとしたら筋違いですよね. あなたが自分で考えればいいだけなのですから.

この回答へのお礼

解決しました ありがとうございました。

お礼日時：2017/07/19 11:41

No.3 回答者： Tacosan 回答日時： 2017/07/18 13:25

帰納法で証明するなら, 一般には

1. 「小さい」場合には直接示す (これを「基底段階」と呼ぶこともある)
2. 「大きい」場合には「小さい」場合に変形できることを示す (こちらは「帰納段階」といったりもする)
という 2ステップとなります.

n=3 とか n=4 とかの具体的な場合が基底段階だね. だからあとは帰納段階をきちんと書けばいい... んだけど, これって n はどこから始めるのが正しいんだろう. n=1 からやらないと, 本当はだめな気もするなぁ.

No.2 回答者： Tacosan 回答日時： 2017/07/18 00:37

実のところあんまりまじめに考えていないんだけど, 「B_1 が最大次数の頂点ではない」ということがいえるなら帰納法で処理できません

かね.

No.1 回答者： Tacosan 回答日時： 2017/07/17 23:13

n=4 だったらどうだろ.