树的性质

下面六个命题是等价的（刻画树）

记 $|V|=n,|E|=m,G=⟨V,E⟩$

• G 连通不含回路（即 G 是树）
• G 中没有回路，且 $m=n-1$
  • 归纳假设证明：至少有一个度数为 1 的结点 $v_0$（一定能找到叶子），删掉它得到 k 的情况
• G 是连通的，且 $m=n-1$
  • 设有 k 个连通分支，证明 k=1
• G 中没有回路，但在 G 中任何两个节点之间增加一条新边，就得到唯一的一条 基本回路
• G 是连通的，但是删除任何一条边就不连通了 树是边数最少的连通图
• G 中每一对结点之间有唯一的一条 基本通路

---

任意非平凡树都至少有两片叶子节点

证明：握手定理 和 $m=n-1$ 性质列不等式

$$\begin{array}{rl}n& =k+2+1+3\\ m& =k+5\\ 4+3+12+k& =2m\end{array}$$

解方程就行

---

满k叉树的节点计算方法