生成树的存在性 定理任何无向连通图都有生成树. 证用破圈法若图中无圈,则图本身就是自己的生成树 否则删去圈上的任一条边,这不破坏连通性,重复进行 直到无圈为止,剩下的图是一棵生成树 推论1设m阶无向连通图有m条边,则m≥n-1. 推论2设m阶无向连通图有m条边,则它的生成树的余树 有mn+1条边 推论3设T为G的生成树T的余树,C为G中任意 个圈,则C与T一定有公共边9 生成树的存在性 定理 任何无向连通图都有生成树. 证 用破圈法.若图中无圈,则图本身就是自己的生成树. 否则删去圈上的任一条边,这不破坏连通性,重复进行 直到无圈为止,剩下的图是一棵生成树. 推论1 设n阶无向连通图有m条边,则mn−1. 推论2 设n阶无向连通图有m条边,则它的生成树的余树 有m−n+1条边. 推论3 设 为G的生成树T 的余树，C 为G 中任意一 个圈，则C与 一定有公共边. T T