木に関する定理

質問

木に対し、それに含まれない辺を１つ加えるとサイクルができ、そのサイクルから任意に辺をとったものは再び木になる。

この証明がわからないのでお願いします。

回答No.2

Tacosan · ベストアンサー

「連結グラフ G = (V, E) で |E| = |V|-1 なら G は木」というのを使うとこんな感じかな:
グラフ G = (V, E) を木とする.
ここに E に属さない辺 e = (u, v) を加えて G' = (V, E') (E' = E ∪ {(u, v)}) とおく.
G は木なので u から v へのパス e1 = (u, v1), e2 = (v1, v2), ..., ek = (vk-1, v) が存在し, これに e を加えると u→v1→v2→...→vk-1→v→u というサイクル C が得られる (これで前半終了).
次にこのサイクル C上の辺 ei = (vi-1, vi) を取り除いて得られるグラフを G'' = (V, E'') (E'' = E' \ {(vi-1, vi)}) とする.
ei = e のときは G'' = G だから木である. そこで ei ≠ e と仮定し, G'' の 2点 x, y ∈ V に対し G'' でパスが存在するかどうか調べる.
1. G における x から y へのパス P が辺 ei を通っていないとき: P は G'' における x から y へのパスでもある.
2. P が辺 ei を通っているとき: 一般性を失うことなく P は x →→→vi-1→vi→→→y と仮定する. G'' には vi-1 から vi への (C を逆にたどる) パス Pi が存在するので, P 中の辺ei を Pi で置き換えることにより新たな (G'' での) x から y へのパスが得られる.
つまり, G'' においても x から y へのパスが存在するので G'' は連結である.
また |E''| = |E| + 1 - 1 = |E| = |V|-1 だから G'' は木である.

お礼

わかりやすい回答ありがとうございました！

回答No.1

Tacosan

「木」をどのように定義していますか?
例えば, 「連結でサイクルを持たないグラフ」と定義すれば, ほとんど自明だと思います. つまり, 加える辺を e = (u, v) とおくと, 木が連結であることから u と v を結ぶパスが存在します. このパスに e を加えるとサイクル C になりますね. そして, C から任意の辺を 1本取り除いても連結であることは明らかでしょう.

補足

回答ありがとうございます。
「木」の定義はおっしゃるとおり「連結でサイクルを持たないグラフ」です。
この自明な証明を何かうまく文章にしたいのですが良い書き方はないでしょうか。