木と探索 連結かつ閉路のないグラフ、道、最長、始点と終点、次数
情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第8章(木と探索)、章末問題8.5の解答を求めてみる。
Gの最も長い道の始点をa、終点とbとする。
aの次数を2以上と仮定すると、 この道には閉路が含まれることになる。
これは、グラフGが閉路を含まないという仮定と矛盾。
よって、aの次数は1である。
bも同様に考え、 その次数は1である。
ゆえに、次数1の頂点が2つ以上存在する。
（証明終）
情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第8章(木と探索)、章末問題8.5の解答を求めてみる。
Gの最も長い道の始点をa、終点とbとする。
aの次数を2以上と仮定すると、 この道には閉路が含まれることになる。
これは、グラフGが閉路を含まないという仮定と矛盾。
よって、aの次数は1である。
bも同様に考え、 その次数は1である。
ゆえに、次数1の頂点が2つ以上存在する。
（証明終）