グラフ理論の教科書には「木の等価条件」として，一見異なる性質がずらっと並んでいます．しかし，これらはすべて同じことを別の言葉で述べているだけです．木とは「余分なものが何ひとつない連結グラフ」であり，その「冗長性ゼロ」という性質が様々な形で表現されているのです．

1 木の定義と直感

直感的に言えば，木は「$n$個の点をちょうど$n-1$本の辺でつないだ，ぎりぎりの連結構造」です．

この木は頂点6個，辺5本です．どの辺を取り除いてもグラフは非連結になり，どこに辺を追加しても閉路ができます．

2 7つの等価条件 ― すべて同じことを言っている

以下の7条件は，$n$頂点のグラフ$G$について，すべて互いに同値です．

一見7つの異なる性質ですが，本質はひとつです．これらをひとつのストーリーで理解しましょう．

3 冗長性ゼロ ― 木の本質

$n$個の頂点を連結にするために最低限必要な辺の数はいくつでしょうか？

つまり，$n-1$本は連結にするための最低コストです．木はこの最低コストをぴったり達成するグラフです．

ここから，等価条件の関係が見えてきます：

条件1（連結 + 閉路なし）$\iff$条件2（連結 + 辺数$n-1$）：もし連結なのに辺が$n$本以上あれば，余分な辺があるわけですから，どこかに閉路ができます．逆に，連結で閉路がなければ辺はぴったり$n-1$本です．

条件4（任意の2点間にちょうど1本の路）：路が0本だと非連結，路が2本以上あると閉路が存在します．「ちょうど1本」は冗長性ゼロの別表現です．

条件5（辺の除去 → 非連結）：余分な辺がないからこそ，どの辺も「橋」として機能しています．1本取ったら壊れるのは，予備がないからです．

条件6（辺の追加 → 閉路）：すでにすべての頂点対間に（ちょうど1本の）路が存在するので，新たに辺を追加すれば2本目の路ができ，閉路が生まれます．

4 辺数の公式の威力

$|E|=n-1$という単純な公式は，驚くほど強力です．

5 根付き木 ― コンピュータサイエンスの主役

コンピュータサイエンスで「木」といえばほぼ根付き木のことです．ファイルシステム，DOM，構文解析木，二分探索木 ― どれも根付き木です．

6 全域木 ― グラフの「骨格」

全域木は，元のグラフの「骨格」です．余分な辺を取り除いて，連結性だけを保った最小限の構造です．

これは直感的に明らかです．連結グラフから，閉路に含まれる辺を1本ずつ除去していけば，いつか閉路がなくなり，木（全域木）が残ります．

7 まとめ

木の美しさは「冗長性ゼロ」という一言に集約されます．7つの等価条件は，この性質を連結性・閉路・辺数・路の一意性・辺の臨界性といった異なる観点から述べたものです．この「ぎりぎりの構造」が，次の記事で扱う貪欲法と深い関係をもちます．