第 6 章：树为什么有 V−1 条边

6.1 树与生成树

在本篇，图由有限个顶点与连接顶点的边组成；平面图中的边是无交叉的线段，只在共同端点相遇。“嵌入”就是这样选定实际点位和线段画法。“度”是某顶点接出的边数。“简单路径”沿图边行走且不重复顶点；“简单回路”沿边走一圈、除起终点外不重复顶点。不要把这里沿原边走的图路径，与第 4 章避开原图走的平面辅助路径混为一谈。

树是有限、连通且没有简单回路的图。生成树保留原图全部顶点，只选取一部分边，并形成树。

生成树为什么存在？只要当前连通图还有回路，就删去回路上的一条边。该边两端仍能沿回路剩余部分连接，所以连通性不变。边数有限，删除过程终止，最后就是生成树。这个构造还没有用到面数或欧拉公式。

6.2 用最长路径找叶子

叶子是度数为 $1$ 的顶点。至少有两个顶点的有限树中，选一条顶点不重复的最长路径，考虑端点 $A$ 。

$A$ 至少有一条相邻边。假如它还有另一条边通向 $B$ ：若 $B$ 不在路径上，就能延长路径；若 $B$ 在路径上，就形成回路。两者都矛盾。因此 $A$ 恰好只有一条相邻边。

图 18｜叶子存在的两个反证分支：第二条边若通向新点，违背最长；若通向旧点，违背无回路。

删除叶子及其边后，剩下的图仍连通：两个剩余顶点间的简单路径不可能以叶子作中间点；也仍无回路。

图 19｜每次删除都让顶点数和边数同时减一。一直删到单点，反过来就得到 E = V−1。

6.3 归纳计数

单顶点树的边数为 $0$ 。对 $V\ge2$ ，删掉一个叶子及其边，剩下 $V-1$ 个顶点。由归纳假设，剩下 $V-2$ 条边，加回被删的一条：

$E=(V-2)+1=V-1.$

这比“每加入一个顶点就加一条边”完整，因为我们先证明了任意有限树都确实可以按这种方式逐步拆开。