形式陈述

对有限简单无向图 $G$，以下条件等价：

1. $G$ 连通且无环；
2. 任意两顶点之间存在唯一简单路径；
3. $G$ 连通且 $|E|=|V|-1$；
4. $G$ 无环且 $|E|=|V|-1$；
5. 删除任一边都会使图不连通；
6. 加入任一非边都会产生唯一环。 这些等价性可通过叶节点归纳和“连通图至少有 $n-1$ 条边、无环图至多有 $n-1$ 条边”组织成短证明闭环。

直觉

树处在连通与含环之间的临界位置：少一条边会断开，多一条边会制造环。

例子与边界

路径图与星图都满足所有刻画。对于无限图，$|E|=|V|-1$ 失去普通整数意义，不能作为等价条件。

推论与应用

它统一生成树、树上归纳、Prüfer 编码以及许多树算法中的唯一父子路径不变量。

参考资料

• Eric Lehman, F. Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science (2018/2024), trees.
• Reinhard Diestel, Graph Theory, 6th ed. (2025), trees and forests.