11.1 定理1#

無向グラフが木であるための必要十分条件は、任意の2つの頂点間に一意な単純経路が存在することである。

証明:
まず、$T$ が木であると仮定する。このとき、$T$ は連結なグラフであり、単純閉路を持たない。$T$ の2つの頂点 $x$ と $y$ を考える。 $T$ が連結であるため、セクション10.4の定理1より、$x$ と $y$ の間には単純経路が存在する。 さらに、この経路は一意であることを示す。もし2つ目の経路が存在すれば、1つ目の経路を $x$ から $y$ まで進み、2つ目の経路を逆順に $y$ から $x$ に戻ることで閉路が形成される。しかし、木には単純閉路が存在しないため、矛盾が生じる。したがって、任意の2つの頂点間の単純経路は一意である。

次に、任意の2つの頂点間に一意な単純経路が存在すると仮定する。このとき、$T$ は連結である。なぜなら、任意の2つの頂点間に経路が存在するからである。また、$T$ は単純閉路を持たないことを示す。 仮に単純閉路が存在するとすれば、その閉路には2つの頂点 $x$ と $y$ を結ぶ2つの異なる単純経路が存在することになる。しかし、これは仮定に反する。したがって、$T$ は単純閉路を持たない。

11.1 定理2#

頂点数が $n$ である木は $n - 1$ 本の辺を持つ。

証明:
この定理を数学的帰納法を用いて証明する。ここで考えるすべての木は根付き木として扱い、根を選ぶものとする。

基礎ステップ:
$n = 1$ の場合、1つの頂点を持つ木には辺が存在しない。したがって、$n = 1$ では定理が成り立つ。

帰納ステップ:
帰納法の仮定として、$k$ 頂点を持つ木は $k - 1$ 本の辺を持つとする。$T$ を $k + 1$ 頂点を持つ木とし、$v$ を $T$ の葉と仮定する（木は有限であるため葉が存在する）。 $w$ を $v$ の親とする。$T$ から $v$ を削除し、$v$ と $w$ を結ぶ辺を取り除くと、$k$ 頂点を持つ木 $T'$ が得られる。 このとき、$T'$ は依然として連結であり、単純閉路を持たない。

帰納法の仮定より、$T'$ は $k - 1$ 本の辺を持つ。したがって、$T$ は $T'$ より1本多く辺を持つ。これは $v$ と $w$ を結ぶ辺が追加されているためである。

11.1 定理3#

内部頂点が $i$ である完全 $m$-分木は $n = mi + 1$ 個の頂点を含む。

証明:
根を除くすべての頂点は、内部頂点の子である。各内部頂点は $m$ 個の子を持つため、根以外の頂点は $mi$ 個存在する。したがって、この木は合計で $n = mi + 1$ 個の頂点を含む。

次に、$T$ を完全 $m$-分木と仮定する。$i$ を内部頂点の数、$l$ を葉の数とする。 この木では、$n$、$i$、および $l$ のいずれか1つがわかれば、他の2つの量も決定される。
定理4 では、これらの量の間の関係を説明している。

11.1 定理4#

完全 $m$-分木に関する関係式:

1. $n$ 個の頂点を持つ場合:
   内部頂点の数: $i = \frac{n-1}{m}$、葉の数: $l = \frac{(m-1)n + 1}{m}$
2. $i$ 個の内部頂点を持つ場合:
   頂点の数: $n = mi + 1$、葉の数: $l = (m-1)i + 1$
3. $l$ 個の葉を持つ場合:
   頂点の数: $n = \frac{ml - 1}{m-1}$、内部頂点の数: $i = \frac{l-1}{m-1}$

証明#

(i) $n$ 個の頂点を持つ場合::

• $n = mi + 1$ から $i = \frac{n-1}{m}$ を得る。
• これを $n = l + i$ に代入すると、葉の数 $l = \frac{(m-1)n + 1}{m}$ となる。

(ii) $i$ 個の内部頂点が与えられた場合:

• $n$ の値は、定義から $n = mi + 1$ である。
• $n = l + i$ という事実を利用すると、葉の数 $l$ は次のようになる: $$l = n - i = (mi + 1) - i = (m-1)i + 1$$ したがって、内部頂点 $i$ に対して、頂点数 $n$ と葉の数 $l$ が求まる。

(iii) $l$ 個の葉が与えられた場合:

• 頂点数 $n$ は、各内部頂点が $m$ 個の子を持つ完全 $m$-分木の性質を用いると、次のようになる: $$n = l + i \quad \text{and} \quad i = \frac{l-1}{m-1}$$ この式を $n = l + i$ に代入する: $$n = l + \frac{l-1}{m-1} = \frac{(m-1)l + (l-1)}{m-1} = \frac{ml - 1}{m-1}$$ これにより、頂点数 $n$ が導かれる。
• 次に内部頂点 $i$ は明らかに: $$i = \frac{l-1}{m-1}$$

11.1 定理5#

$h$ の高さを持つ $m$-分木（$m$-ary tree）において、葉の数は最大 $m^h$ である。

証明:

この証明は高さに関する数学的帰納法を用いる。

まず、高さ1の $m$-分木を考える。この木は根と最大 $m$ 個の子を持ち、それらはすべて葉である。したがって、葉の数は最大で $m^1 = m$ である。これが帰納法の基礎ステップである。

次に、任意の高さ $h$ 未満の $m$-分木についてこの結果が成り立つと仮定する。これを帰納法の仮定とする。
$T$ を高さ $h$ の $m$-分木とする。$T$ の葉は、根からレベル1の各頂点へとエッジを削除して得られる $T$ の部分木の葉である。

これらの部分木の高さは $h-1$ 以下である。したがって、帰納法の仮定より、各部分木の葉の数は最大 $m^{h-1}$ である。さらに、これらの部分木の数は最大 $m$ であるため、全体の葉の数は

となる。これにより、根付き木 $T$ の葉の数が最大 $m^h$ であることが示された。

これで帰納法による証明が完了する。

11.1 系1#

高さ $h$ の $m$-分木（$m$-ary tree）に葉の数が $l$ 個あるとき、

が成り立つ。もし $m$-分木が完全かつ平衡であるならば、

（ここで、天井関数 $\lceil x \rceil$ は、$x$ 以上の最小の整数を表す）。

証明:

定理5より、葉の数 $l$ に対して $l \leq m^h$ が成り立つ。底 $m$ で対数を取ると、

となる。$h$ は整数であるため、

が成り立つ。

次に、木が平衡であると仮定する。すると、各葉は高さ $h$ または $h-1$ のレベルに存在する。そして、高さが $h$ であるため、レベル $h$ に少なくとも1つの葉が存在する。 これにより、葉の数は $m^{h-1}$ より多い必要がある（演習30を参照）。
また、$l \leq m^h$ であるため、

が成り立つ。この不等式に底 $m$ の対数を取ると、

が得られる。

したがって、$h$ は

であることが示される。

11.1.14#

単純グラフ $T$ が木であるための必要十分条件は、$T$ が連結であり、かつ任意の辺を削除すると非連結グラフになることである。

証明:

まず、$T$ が木であると仮定する。定義より $T$ は連結であり、任意の辺を削除すると非連結グラフになることを示す。
$\{x, y\}$ を $T$ の辺とする。このとき $x \neq y$ である。$T$ から $\{x, y\}$ を削除したグラフは、$x$ から $y$ への経路が存在しない。 なぜなら、$T$ では $x$ から $y$ への単純な経路が唯一であり、その経路に $\{x, y\}$ が含まれていたからである。 （定理1より、頂点 $u$ から頂点 $v$ への経路が存在するならば、単純経路も存在する。）
したがって、$\{x, y\}$ を削除すると非連結グラフになる。

次に、$T$ が連結であり、任意の辺を削除すると非連結になると仮定する。$T$ が木であることを示す。 $T$ が木でない場合、$T$ には単純閉路（サイクル）が存在する。 例えば、閉路を $x_1, x_2, \dots, x_r, x_1$ とする。$T$ から辺 $\{x_r, x_1\}$ を削除しても、グラフは連結のままである。 なぜなら、削除された辺が経路に使用されていたとしても、閉路の他の部分（$x_1, x_2, \dots, x_r$ またはその逆順）を使って連結性を保つことができるからである。
これは仮定「任意の辺を削除すると非連結になる」に反する。したがって、$T$ は木である。

11.1.15#

$n$ 個の頂点を持つ単純グラフ $G$ について、次を示せ：
a. $G$ は $n - 1$ 本の辺を持つ連結グラフであるとき、かつそのときに限り木である。
b. $G$ は $n - 1$ 本の辺を持ち、単純閉路を持たないとき、かつそのときに限り木である。

証明:

a.
「ならば」部分
$G$ が木であるならば、それは連結であり閉路を持たない。そのため、$G$ の辺の数は $n - 1$ である（Theorem 2）。

「必要条件」部分
$G$ が連結な単純グラフであり、$n - 1$ 本の辺を持つと仮定する。もし $G$ が木でない場合、Exercise 14 により $G$ には取り除くことで連結なグラフ $G'$ を生成できる辺が存在する。この操作を繰り返し、最終的に木が得られる。 この操作には高々 $n - 1$ 回の辺の削除が必要であるが、もともと $G$ は $n - 1$ 本の辺しか持たないため、削除は行われない。したがって、$G$ は初めから木であった。

b.
「ならば」部分
$G$ が木であるならば、それは $n - 1$ 本の辺を持ち、定義から単純閉路を持たない。

「必要条件」部分
$G$ が $n - 1$ 本の辺を持ち、単純閉路を持たないと仮定する。$c$ を $G$ の連結成分の数とする。それぞれの成分が $n_i$ 個の頂点を持つとする。このとき、

である。また、各成分について、辺の総数は $\sum_{i=1}^c (n_i - 1)$ となる。よって、

問題の仮定より、$n - c = n - 1$ となる。したがって、$c = 1$ が導かれる。つまり、$G$ は連結であり、木の定義を満たす。

11.1.30#

高さ $h$ の完全 $m$-分平衡木（full $m$-ary balanced tree）において、葉の数は $m^{h-1}$ よりも多いことを示せ。

証明:

$m \geq 2$ と仮定する。まず、レベル $h$ にあるすべての頂点を削除する。レベル $h$ には少なくとも1つの頂点が存在し、それらはすべて葉である。
このとき、結果として得られる木は高さ $h-1$ の完全 $m$-分木である。演習28の結果より、この木の葉の数は $m^{h-1}$ である。

しかし、元の木では、レベル $h-1$ にあるすべての内部頂点がレベル $h$ に少なくとも2つの葉を生成する。したがって、元の木の葉の数は $m^{h-1}$ よりも多くなる。

11.1.44#

すべての木は2色で彩色することができる。

証明:

根を1つ選び、それを赤色で塗る。その後、奇数レベルのすべての頂点を青色で塗り、偶数レベルのすべての頂点を赤色で塗る。この彩色方法により、隣接する頂点は必ず異なる色で塗られるため、木全体が2色で彩色可能である。

11.1.48#

$n$ 頂点を持つ二分木において、葉の平均深さが $\Omega(\log n)$ であることを示せ。

証明:

$T$ を高さ $h$ を持つ $n$ 頂点の二分木とする。

1. 頂点の移動:
   $h-1$ のレベルに子が2つない内部頂点が存在する場合、レベル $h$ にある葉をその欠損部分の子として移動させる。この操作によって、木の葉の平均深さは低くなるが、証明すべき下限には影響しない。 したがって、操作後の木について証明すれば十分である。

2. 完全な二分木の構築:
   この操作を繰り返すことで、$h-1$ レベル以下に2つの子を持たない内部頂点が存在しなくなる。結果として、すべての葉はレベル $h-1$ および $h$ に集まる。 次に、レベル $h$ にあるすべての頂点を削除し、レベル $h-1$ に集約する。

3. 頂点数の計算:
   頂点数 $n$ に対する変化は最大でも係数2（またはそれより少し多い程度）であり、大きなオメガ記法（$\Omega$）に対する影響は無視できる（$\log n$ が1程度しか変化しないため）。
   完全二分木では、演習28より、葉の数は $2^{h-1}$ であり、$n = 2^h - 1$ が成り立つ。

4. 葉の平均深さ:
   完全二分木において、すべての葉は深さ $h-1$ にある。ここで、$n = 2^h - 1$ より、

   $$h \approx \log_2 n$$

   したがって、葉の平均深さは $\Omega(\log n)$ であることが示された。

11.2 定理1#

二分比較に基づくソートアルゴリズムは、少なくとも $\lceil \log_2 n! \rceil$ 回の比較を必要とする。

証明:

1. ソートの複雑度の定義:
   ソートアルゴリズムの複雑度は、使用される二分比較の回数で測定される。最悪の場合の比較回数は、ソート手順を表す決定木（decision tree）の高さに等しい。

2. 決定木と高さの関係:
   $n$ 要素のリストをソートするための決定木には、$n!$ 通りの葉が存在する。これは、ソートのすべての順列に対応する。
   二分木の高さは、葉の数 $n!$ に対して

   $$\lceil \log_2 n! \rceil$$

   以上であることが系1（11.1節）から導かれる。

3. 結論:
   よって、$n!$ 個の葉を持つ二分決定木の高さは少なくとも $\lceil \log_2 n! \rceil$ であり、これはソートアルゴリズムに必要な比較回数の下限である。

11.2 系1#

二分比較に基づくソートアルゴリズムが $n$ 個の要素をソートする際の比較回数は $\Omega(n \log n)$ である。

証明:

• 定理1の結果: 定理1より、二分比較に基づくソートアルゴリズムが必要とする比較回数は少なくとも $\lceil \log_2 n! \rceil$ である。

• 階乗の対数の評価:
  演習74（Section 3.2）より、$\log_2 n!$ は $\Theta(n \log n)$ である。これは、アルゴリズムの計算量解析における標準的な参照関数である。

• 結論:
  よって、$n$ 個の要素をソートするために二分比較を使用するアルゴリズムは、最悪の場合において少なくとも

  $$\Omega(n \log n)$$

  回の比較が必要である。

これにより、系1が示された。

11.2 定理2#

二分比較に基づくソートアルゴリズムが $n$ 個の要素をソートする際に使用する平均比較回数は $\Omega(n \log n)$ である。

証明:

1. 最悪ケースの比較回数:
   系1より、二分比較に基づくソートアルゴリズムが $n$ 個の要素をソートする際の最悪ケースの比較回数は $\Theta(n \log n)$ である。これにより、マージソートのようなアルゴリズムがこの複雑度において最適であることが分かる。

2. 平均ケースの証明:
   平均ケースでも類似の結果が成り立つことを示す。

   • 平均比較回数は、決定木における葉の平均深さに等しい。
   • 演習48（11.1節）より、$N$ 頂点を持つ二分木における葉の平均深さは $\Omega(\log N)$ である。

3. 階乗関係の利用:
   $N = n!$ とおくと、葉の平均深さが $\Omega(\log N)$ であることから、$N = n!$ に対応する関数 $\log n!$ は $\Theta(n \log n)$ である。 したがって、平均比較回数も

   $$\Omega(n \log n)$$

   である。

以上により、定理3が示された。

11.4 定理1#

単純グラフ $G$ は、全域木を持つ場合に限り連結である。

証明:

（必要条件）
まず、単純グラフ $G$ が全域木 $T$ を持つと仮定する。
$T$ は $G$ の全ての頂点を含み、さらにその頂点間にパスが存在する。このとき、$T$ は $G$ の部分グラフであるため、$G$ においても任意の2つの頂点の間にパスが存在する。したがって、$G$ は連結である。

（十分条件）
次に、$G$ が連結であると仮定する。
もし $G$ が木でない場合、$G$ は単純閉路（サイクル）を含む。その閉路から1つの辺を削除する。このとき、生成される部分グラフは1本少ない辺を持ちながら、$G$ の全ての頂点を含み、かつ連結である。この部分グラフは依然として連結である。なぜなら、削除された辺を含む閉路上の任意の2つの頂点は、削除された辺を含まないパスによって依然として結ばれるためである。

この操作を繰り返すことで、$G$ 内の全ての単純閉路が削除される。グラフに含まれる辺の数は有限であるため、このプロセスは有限回の手順で終了する。その結果として、閉路を持たない連結なグラフが残る。このグラフは木であり、$G$ の全ての頂点を含むため、全域木である。

11.4.25#

連結単純グラフ $G$ において、頂点 $v$ を根とする幅優先全域木（breadth-first spanning tree）における $u$ のレベル数は、$v$ から $u$ への最短経路の長さに等しいことを示せ。

証明:

帰納法を経路の長さに基づいて示す。

1. 基礎ステップ（経路の長さが0の場合）:
   経路の長さが0であれば、$v = u$ であり、結果は自明である。$u$ は根 $v$ と同じレベル（レベル0）にある。

2. 経路の長さが1の場合:
   経路の長さが1の場合、$u$ は $v$ に隣接している。したがって、幅優先全域木において $u$ はレベル1に配置される。

3. 帰納法の仮定:
   経路の長さが $l$ 以下のすべての頂点 $u'$ に対して、$u'$ のレベルは $v$ から $u'$ への最短経路の長さに等しいと仮定する。

4. 経路の長さが $l+1$ の場合:
   経路の長さが $l+1$ の場合、$v$ から $u$ への最短経路上にある $u$ の直前の頂点を $u'$ とする。 帰納法の仮定より、$u'$ は幅優先全域木のレベル $l$ にある。

   • $u$ がレベル $l$ 以下にあったと仮定すると、$v$ から $u$ への最短経路の長さも $l$ 以下になる。これは $u$ が直前の頂点 $u'$ に隣接していることに矛盾する。
   • よって、$u$ は幅優先全域木において $u'$ の隣接頂点として、レベル $l+1$ に追加される。

以上により、帰納法により証明が成立する。

11.4.55#

$T_1$ および $T_2$ を単純グラフ $G$ の2つの全域木（spanning trees）とする。また、$e_1$ を $T_1$ に含まれ、$T_2$ に含まれない辺とする。 このとき、$T_2$ に含まれ、$T_1$ に含まれない辺 $e_2$ が存在して、次の性質が成り立つことを示せ：

• $T_1$ から $e_1$ を削除し、$e_2$ を加えたものは全域木である。
• $T_2$ から $e_2$ を削除し、$e_1$ を加えたものは全域木である。

証明:

1. $T_2 \cup \{e_1\}$ における閉路の存在:
   $e_1$ を $T_2$ に加えると、$T_2 \cup \{e_1\}$ は単純閉路 $C$ を含む。この閉路 $C$ は $e_1$ を含む。

2. $T_1 - \{e_1\}$ の連結成分:
   $T_1$ から $e_1$ を削除すると、グラフ $T_1 - \{e_1\}$ は2つの連結成分に分かれる。$e_1$ の端点 $u$ と $v$ は、これら2つの異なる成分に属する。

3. 閉路 $C$ 上の $e_2$ の選択:
   $C$ 上を $u$ から $e_1$ の方向とは逆に進むと、$v$ と同じ成分に初めて到達する頂点が存在する。その際に交差する辺を $e_2$ とする。

4. $T_2 \cup \{e_1\} - \{e_2\}$ は全域木である:
   $e_2$ は閉路 $C$ 上に存在するため、$e_2$ を削除すると閉路が解消される。したがって、$T_2 \cup \{e_1\} - \{e_2\}$ は依然として連結かつ $G$ のすべての頂点を含む木となる。

5. $T_1 - \{e_1\} \cup \{e_2\}$ は全域木である:
   $T_1 - \{e_1\}$ は2つの連結成分に分かれているが、$e_2$ はこの2つの成分を結合する。したがって、$T_1 - \{e_1\} \cup \{e_2\}$ は再び連結かつすべての頂点を含む木となる。

結論:
以上により、$e_2$ は条件を満たす辺であり、次の性質が示された：

• $T_1 - \{e_1\} \cup \{e_2\}$ は全域木である。
• $T_2 \cup \{e_1\} - \{e_2\}$ は全域木である。

11.4.56#

任意の全域木 $T_1$ から任意の別の全域木 $T_2$ へ、辺を1つずつ削除し別の辺を加える操作を繰り返すことで到達できることを示せ。

証明:

1. 前問（Exercise 55）の利用:
   問題55により、$T_1$ に含まれ $T_2$ には含まれない辺 $e_1$ を削除し、 $T_2$ に含まれ $T_1$ には含まれない辺 $e_2$ を加えることで、$T_1$ を新しい全域木に変換することが可能である。

2. 距離の定義:
   $T_1$ と $T_2$ の間の距離 $d$ は、それらの木の辺集合の対称差（$T_1$ と $T_2$ の共通でない辺の数）を2で割ったものである（各操作で2つの辺が入れ替わるため）。

3. 操作による変換:

   • 一度の操作で、$T_1$ に含まれる辺 $e_1$ を削除し、$T_2$ に含まれる辺 $e_2$ を加えることで、$T_1$ と $T_2$ の間の距離を2減少させることができる。
   • この操作を繰り返すことで、距離 $d$ を0にすることができる。

4. 帰納法的な手続き:
   初めに $T_1$ と $T_2$ の距離が $d$ であるとする。各ステップで次の操作を行う：

   • $T_1$ に含まれるが $T_2$ には含まれない辺 $e_1$ を選ぶ。
   • $T_2$ に含まれるが $T_1$ には含まれない辺 $e_2$ を選び、$T_1$ から $e_1$ を削除し、$e_2$ を加える。
     この操作により、距離 $d$ は2減少する。

5. 終了条件:
   距離 $d$ が0になるとき、$T_1$ は $T_2$ と完全に一致する。

結論:
この手順を $d$ 回繰り返すことで、任意の全域木 $T_1$ から任意の別の全域木 $T_2$ へ到達することができる。

11.5.18#

連結な重み付きグラフにおいて、最小重みの辺は任意の最小全域木に含まれなければならないことを示せ。

証明:

反証法を用いる。

1. 仮定:
   最小重みの辺 $e$ がある最小全域木 $T$ に含まれていないと仮定する。

2. 辺 $e$ の追加による閉路の形成:

   • $e$ を $T$ に追加すると、$T \cup \{e\}$ はグラフ全体を覆うが、閉路（単純サイクル）$C$ が1つ含まれることになる。
   • 閉路 $C$ は $e$ を含む。

3. 閉路から辺を削除:
   閉路 $C$ には $e$ 以外の辺も存在し、それらは $e$ よりも大きな重みを持つ（仮定より $T$ の辺はすべて $e$ よりも重みが大きい）。

   • $C$ の中から $e$ 以外の任意の辺 $e'$ を削除すると、新しいグラフ $T' = T \cup \{e\} - \{e'\}$ は連結かつサイクルを含まないため、再び全域木となる。

4. 矛盾の導出:

   • $e'$ の重みは $e$ より大きいため、$T'$ の重みの合計は $T$ の重みより小さくなる。
   • これは $T$ が最小全域木であるという仮定に矛盾する。

結論:
したがって、最小重みの辺 $e$ は任意の最小全域木に含まれなければならない。

11.5.19#

すべての辺の重みが異なる場合、連結な重み付きグラフにおける最小全域木は一意であることを示せ。

証明:

1. 仮定:
   連結な重み付きグラフ $G$ において、すべての辺の重みが異なるとする。さらに、最小全域木が2つ存在すると仮定し、それらを $T_1$ と $T_2$ とする。

2. 反証法の適用:
   $T_1$ と $T_2$ は異なる全域木であるため、辺の集合において異なる部分が存在する。つまり、$T_1$ に含まれ $T_2$ に含まれない辺 $e_1$ が少なくとも1つ存在する。

   • $e_1$ を $T_2$ に加えると閉路 $C$ が形成される。

3. 閉路 $C$ に含まれる辺:
   $C$ の中には $e_1$ 以外に $T_2$ に含まれる辺が存在する。その中から任意の辺 $e_2$ を選ぶと、$e_1$ の重みと $e_2$ の重みを比較することができる。

4. 重みの矛盾:

   • $e_1$ の重みが $e_2$ より小さい場合、$T_2$ から $e_2$ を削除し $e_1$ を加えることで、$T_2$ の重みの合計は小さくなる。 これは $T_2$ が最小全域木であるという仮定に矛盾する。
   • $e_1$ の重みが $e_2$ より大きい場合、$T_1$ に対して同様の操作を行うと $T_1$ の重みの合計が小さくなる。これは $T_1$ が最小全域木であるという仮定に矛盾する。

5. 結論:
   すべての辺の重みが異なる場合、最小全域木は一意に決定される。したがって、仮定した2つの異なる最小全域木 $T_1$ と $T_2$ は存在しない。

補完1#

単純グラフが木であるための必要十分条件は、次の2つを満たすことである：

1. 単純閉路を含まない。
2. 隣接していない2つの頂点を結ぶ辺を追加すると、ちょうど1つの単純閉路を持つ新しいグラフが生成される。

証明:

「ならば」部分
$T$ が木であると仮定する。このとき、$T$ は明らかに単純閉路を含まない。
$T$ に隣接していない頂点 $u$ と $v$ を結ぶ辺 $e$ を追加すると、$e$ により新しいグラフに閉路が形成される。これは、$e$ と $u$ から $v$ への $T$ 内の唯一のパスによって構成される。 $T$ が木であるため、辺 $e$ の追加により生成される閉路は1つのみである。

「十分条件」部分
$T$ が定理の条件を満たすと仮定する。このとき、$T$ が連結であることを示せばよい。
$T$ が連結でないと仮定する。この場合、$u$ と $v$ が異なる連結成分に存在する場合、辺 $e = \{u, v\}$ を追加しても単純閉路は形成されない。これは、定理の条件に矛盾する。したがって、$T$ は連結である。

さらに、$T$ は単純閉路を持たないことが仮定されているため、$T$ は木の定義を満たす。

補完3#

少なくとも1本の辺を持つすべての木は、少なくとも2つのペンダント頂点（次数が1の頂点）を持つ。

証明:

木 $T$ が $n$ 個の頂点を持ち、それぞれの頂点の次数を $d_1, d_2, \dots, d_n$ とする。木の性質から、次の式が成り立つ：

ここで、$e$ は木の辺の本数である。また、木では $e = n - 1$ であるため：

各頂点の次数 $d_i$ は少なくとも1以上であるため：

これを整理すると：

この式から、和の中で $d_i - 1$ が1以上となる項は高々 $n - 2$ 個しか存在し得ない。したがって、少なくとも2つの頂点に対して $d_i - 1 = 0$ が成り立つ、すなわち $d_i = 1$ である。

これにより、少なくとも2つの頂点がペンダント頂点であることが示された。

補完6#

$d_1, d_2, \ldots, d_n$ を正の整数とし、その和が $2n - 2$ であるとする。このとき、$n$ 個の頂点を持つ木で、頂点の次数が $d_1, d_2, \ldots, d_n$ であるものが存在することを示せ。

証明: 数学的帰納法を用いて示す。

基本ステップ
$n \leq 2$ の場合、問題は自明である。実際、$n = 2$ の場合、$d_1 = d_2 = 1$ であり、1本の辺を持つ木がこの条件を満たす。

帰納ステップ
$n \geq 3$ と仮定する。このとき、正の整数 $d_i$ の少なくとも1つは $1$ である必要がある。 なぜなら、$n$ 個のすべての $d_i$ が2以上である場合、その和は少なくとも $2n$ となり、条件 $\sum d_i = 2n - 2$ に矛盾するためである。

一般性を失うことなく、$d_n = 1$ と仮定する。このとき、残りの $d_1, d_2, \ldots, d_{n-1}$ がすべて1であることはあり得ない。なぜなら、条件 $\sum d_i = 2n - 2$ により、$2n - 2 > n$ であるためである。

次に、帰納法の仮定を用いて、列 $d_1 - 1, d_2, \ldots, d_{n-1}$ に対して木が存在することを仮定する。 この木に新しい頂点を追加し、次数が $d_n = 1$ であるように辺を接続することで、頂点の次数が $d_1, d_2, \ldots, d_n$ である木を構築できる。

したがって、すべての $n$ に対して定理が成立することが示された。

補完7#

すべての木は平面グラフであることを示せ。

証明：

木は単純閉路を持たないため、$K_{3,3}$ や $K_5$ の部分グラフに同相であるような部分グラフを含むことはない。したがって、木は平面グラフである。

補完8#

すべての木は二部グラフであることを示せ。

証明：

木を根付き木として考える。頂点を偶数レベルの頂点集合と奇数レベルの頂点集合に分ける。この分割により、隣接する任意の2頂点は異なる集合に属するため、木は二部グラフである。

補完9#

すべての森は2色で彩色可能であることを示せ。

証明：

森の各連結成分に対して、それぞれ独立に彩色を行う。まず、各連結成分を根付き木として設定する。その後、偶数レベルのすべての頂点を赤色で、奇数レベルのすべての頂点を青色で彩色する。これにより、各連結成分が正しく彩色され、森全体が2色で彩色可能であることが示される。