定义:不含任何回路的连通图成为树。度为1的点称为树叶,大于1的点称为分支点。

定义:设e是图G的一条边。如果\(G-e\)的连通分支多于G,称e是G的一条割边。

定理1. e是G的割边,当且仅当e不属于G的任何回路。

定理2. 设T是阶不小于2的无向简单图,则以下说法等价:

下面说明G中任意回路都可由基本回路生成。

定理5. 连通图G的任何回路C均可表示为生成树T的若干基本回路的环和。

定义:设\(S\)是图G的边集E的子集,且满足:

定理7. 设T是连通图G的生成树,则T的每一树枝对应G的一个割集。

由定理7可以引出基本割集系统的概念。基本割集系统与基本回路系统有类似的性质。

定理8. 连通图G的每个割集必包含G中每棵生成树的至少一个树枝。

证明与定理3类似。

为了说明任意割集可由基本割集生成,我们还需引入断集的概念。

割集一定是断集,但断集未必是割集。

定理11. 连通图G的任意割集可以表示为生成树T的对应若干基本割集的环和。

定理12. 任何一个回路与任何一个断集都有偶数条公共边。