双循环，对集和树

令Ｇ＝（Ｖ，Ｅ）为一个图，它的节点数为ｎ，不仅是一个双循环也是一个上循环．记β（Ｇ）为Ｇ的双循环空间的维数．对于Ｇ的一个子图Ｈ，用φ（Ｇ，Ｈ）表示Ｇ的支撑森数目，使得它的每个树均恰含Ｈ的一条边．图Ｇ的Ｈ扩张Ｘ（Ｇ，Ｈ）在Ｇ上增添一个新节点ν，连ν与Ｈ的每一个奇次节点以一边所得到的图．本文证明，φ（Ｇ，Ｈ）是个偶数，要么Ｘ（Ｇ，Ｈ）不连通，要么Ｘ（Ｇ，Ｈ）有一个非零双循环．对于一个欧拉图Ｇ，令λ（Ｇ）为Ｇ中这样边的最小数目，使得在将它们从Ｇ中收缩掉而得到的图Ｇ中，所有那些落在奇数个完满对集上的边，形成一个非零双循环．同时还得到，在Ｇ的最大对集中边数为μ（Ｇ）的一个下界，即μ（Ｇ）≥（ｎ－｜β（Ｇ）－１｜）／２．对于非欧拉图Ｇ，令ψ（Ｇ）＝β（Ｘ（Ｇ，Ｇ）），和用γ（Ｇ）表示这样边的最小数目，使得在将它们从Ｇ中收缩掉而得到的图上，有边属于奇数个完满对集．我们证明，γ（Ｇ）＝ψ（Ｇ）以及μ（Ｇ）≥（ｎ－ψ（Ｇ））／２．