帰納法の証明で後一歩

質問

帰納法というんでしょうか、証明する問題を解いていますが後一歩でどうすればよいのか分かりません。
というか自分のやったところも書き方とかあっているかどうか分かりません。
問題の"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|でいいと思うんですが、それが私の出来る精一杯です。
これからどうすればいいのか教えてください。

回答No.4

kony0

>Cycleが含まれるグラフだとVよりも大きくなるような気が…。

「|V|以上の道のりとなるpathが存在しないことを示す」のではなく、「|V|-1以下の道のりとなるpathが存在する」ことを示すだけですよね。
cycleが含まれるwalk（当該walkのlengthは|V|以上のこともあり得る）があったとき、そのcycleに入り込まないpathを選ぶことは可能です。
そしてcycleに入り込まないpathは同じvertexを２度通過することはなく、そのlengthが|V|-1以下なのは、皆様がおっしゃられるとおり明らかです。

・・・という趣旨の問題じゃないかと思われますが、どうでしょう？

お礼

vi から vj への path の中に同じ点が現れたならば、
vi ... vk ... vk ... vj を
vi ... vk ... vj とすることでもっと短かい path を作れる。

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

回答No.3

graphaffine

訂正です。

誤：任意の歩道が道を含む事を示せば、長さが|V|-1になるのは、道の定義から明らかです。

正：任意の歩道が道を含む事を示せば、長さが|V|-1未満になるのは、道の定義から明らかです。

回答No.2

graphaffine

ginkgoさん、今晩は。グラフ理論の話ですね。

問題の訳（意味が取れる最小限に圧縮）
２点の間に歩道が有れば、その2点を結ぶ長さ |V|-1未満の道が有る。

任意の歩道が道を含む事を示せば、長さが|V|-1になるのは、道の定義から明らかです。

道（path）、歩道（walk）の定義の理解がしっかりしていないようです。確認して下さい。
それから、|V|は（頂点）集合Vの要素数です。「Vの全体の長さ」という言葉は意味がありません。

なお、ここで用いた訳語が標準的とは限りませんので、和文の書籍を読むときは御注意下さい。

お礼

vi から vj への path の中に同じ点が現れたならば、
vi ... vk ... vk ... vj を
vi ... vk ... vj とすることでもっと短かい path を作れる。

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

回答No.1

haus

v_iとv_jを結ぶ経路が、|V|以上の長さであれば 、
|V|-1よりも小さいか等しい長さの経路に帰着できることを示してはダメなのでしょうか？

お礼

vi から vj への path の中に同じ点が現れたならば、
vi ... vk ... vk ... vj を
vi ... vk ... vj とすることでもっと短かい path を作れる。

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