三、割集与回路 定理74:任何一条回路和任何生成树的余树至 少有一条公共边。 证明:如果一条回路和一棵生成树的余树没有 公共边,则这回路含在该生成树中,这是不可能 的。 定理75:任何一个割集和任何生成树至少有一 条公共边。 证明:如果一个割集和一棵生成树没有公共边, 则删去该割集后留下一棵完整的生成树, 也就是说,删去一个割集后,不能将图G分为两 个分支,这与割集的定义相矛盾。三、割集与回路 定理7.4：任何一条回路和任何生成树的余树至 少有一条公共边。 证明：如果一条回路和一棵生成树的余树没有 公共边, 则这回路含在该生成树中, 这是不可能 的。 定理7.5：任何一个割集和任何生成树至少有一 条公共边。 证明：如果一个割集和一棵生成树没有公共边, 则删去该割集后留下一棵完整的生成树, 也就是说, 删去一个割集后, 不能将图G分为两 个分支, 这与割集的定义相矛盾