证明: 若T中只有一片树叶,则∑(v)≥2(m +1=2m-1 若7中没有树叶,则Σd(v)≥2m 均与Σ1y)=2=2(n-1)矛盾,所以在任 棵非平凡树T中,至少有两片树叶
证明： 若T中只有一片树叶，则 d(vi)≥2(n- 1)+1=2n-1。 若T中没有树叶，则d(vi)≥2n。 均与d(vi)=2e=2(n-1)矛盾，所以在任 一棵非平凡树T中，至少有两片树叶
10.2生成树与割集 生成树 1定义10.2(生成树) 图G的生成子图是树T,称T为G的生成 树 从G中删去T的边,得到的图称G的余枝, 记为7。 T中的边称为树枝(或枝) ⑦中的边称为G的弦(或连枝)
10.2 生成树与割集 一、生成树 1 定义10.2（生成树） 图G的生成子图是树T，称T为G的生成 树。 从G中删去T的边，得到的图称G的余枝， 记为Ť。 T中的边称为树枝（或枝）。 Ť中的边称为G的弦（或连枝）
注: (1)由定义知,只有连通图才有生成树。 (2)连通图的生成树不唯一,至少有一棵, 因通过不断地删去图G中的回路中的边, 总能得到一棵生成树
注： (1)由定义知，只有连通图才有生成树。 (2)连通图的生成树不唯一，至少有一棵， 因通过不断地删去图G中的回路中的边， 总能得到一棵生成树
定理10.3 G是连通图>G有生成树 证明方法:→构造性,<连通证明方法
定理10.3 G是连通图G有生成树。 证明方法：构造性, 连通证明方法
10.2生成树与割集 2定义10.3(秩,零度) 设图G有n个顶点,e条边,个分支, 称n-0为图G的涨,称e-n+0为图G的零度 G的秩是G的各分支中生成树的枝数之 和。 G的零度是G的各分支中生成树的连枝 数之和
10.2 生成树与割集 2 定义10.3（秩，零度） 设图G有n个顶点，e条边，个分支， 称n-为图G的秩，称e-n+为图G的零度。 G的秩是G的各分支中生成树的枝数之 和。 G的零度是G的各分支中生成树的连枝 数之和