帰納法の証明で後一歩
帰納法というんでしょうか、証明する問題を解いていますが後一歩でどうすればよいのか分かりません。
というか自分のやったところも書き方とかあっているかどうか分かりません。
問題の"any graph"というのも引っ掛かります。
Cycleが含まれるグラフだとVよりも大きくなるような気が…。
これがその問題です。
Let G = (V, E) be any graph. Prove the following claim: If there is any walk between vi ∈ V and vj ∈ V, then there must be a path of length no larger than |V|-1 between these two vertices.
G = (V, E)はどんなタイプのグラフでもよいとする。次の主張を証明せよ: もしvi ∈ Vとvj ∈ Vの間にいくらかの歩行距離があれば、それらの二つの頂点の間には|V|-1よりも大きくない(つまり|V|-1よりも小さいか等しい)長さの経路が存在するはずである。
※ちなみに|V|はVの絶対値ではなく、Vの全体の長さです。例えばV={v1, v2, v3}であれば|V|=3です。
自分のやったところまで書きます。
証明: もしvi ∈ Vとvj ∈ Vの間にいくらかの歩行距離があれば、
|(vi, vj)| <= |V|-1
であることを証明したい。
根拠: P(1)は真である、なぜなら
|(v1, v2)| <= |{v1, v2}|-1
1 <= 2-1
1 <= 1
帰納的仮定:
P(K)が真だと仮定すると
|(v1, v2)(v2, v3)(v3, v4), ... ,(v_K-1, v_K)| <= |K|-1
そしてP(K+1)が真であることも証明しないといけないので
|(v1, v2)(v2, v3)(v3, v4), ... ,(v_K-1, v_K)(v_K, v_K+1)| <= |K+1|-1
…これからどうすればいいのか分かりません。
|K+1|-1の部分はそのまま1をプラスマイナスして0なので
|K|でいいと思うんですが、それが私の出来る精一杯です。
これからどうすればいいのか教えてください。
