木と探索 連結グラフ、頂点の総数、辺の総数、等式、必要条件、十分条件、閉路
情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第8章(木と探索)、章末問題8.1の解答を求めてみる。
Gに閉路があると仮定する。
eをその閉路の1つの辺とする。
このとき、 Gからeを除いたグラフを
とすると、このグラフは連結である。
また、
これは
が連結であることと矛盾。
よって、 Gに閉路は存在しない。
と隣接しない頂点とする。
このとき、Gは連結なので、Gに辺
を加えると閉路ができる。