在证明之前先引进一些概念和结果。设[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]是图[tex=4.143x1.357]xwGSF18Bx910Lmy2fW5mI6LjzjNCbP2UGt+pnxYqIW8=[/tex]的生成树，由于图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]有[tex=0.5x0.786]WKYr2kz69xrVCyPvbyVG1w==[/tex]条边，[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]的结点数等于[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的结点数[tex=1.357x1.214]7llls+HoRqMzVH8M3Zep4w==[/tex]有[tex=1.786x1.143]v+TGC5V/bwS1rZOtFfmJdA==[/tex]条边，故对于[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]共有[tex=3.071x1.143]Rqwb12XXeEj3LHpEY76QPw==[/tex]条弦， 把任意一条弦加到[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]中，恰得到一个回路，这种回路称之为基本回路，共有[tex=3.071x1.143]Rqwb12XXeEj3LHpEY76QPw==[/tex]个基本回路。任一基本回路恰有一条弦，其他均为树枝。另外，从[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]中删去一条树枝，[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]就分成两棵不连通的树[tex=1.0x1.214]W9y/AChQ6cjPFh4mePUysQ==[/tex]和[tex=1.0x1.214]zUvLEpcJP27MfHQYIgGtCA==[/tex]， 令[tex=2.357x1.214]JWlnJuITOkFpF8IUU2nufw==[/tex]分别为它们的结点集合，删去[tex=1.0x1.214]HiDC35DFbXeLtzUYzu14OQ==[/tex]与[tex=1.0x1.214]jO6biZi3g6qido2CiR3jLg==[/tex]之间所有边，就将图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]分成两个不连通的分图[tex=1.143x1.214]tVkSXDTbP2YDKnpeqXNXXg==[/tex]和[tex=1.143x1.214]z/iyGGP+DXie1qfllHTsVg==[/tex]，这些边与[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]中所删去的树枝一起组成了图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的一个割集，这个割集称为基本割集，因为[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]共有[tex=1.786x1.143]v+TGC5V/bwS1rZOtFfmJdA==[/tex]条边，所以共有[tex=1.786x1.143]v+TGC5V/bwS1rZOtFfmJdA==[/tex]个基本割集。任一基本割集中恰有一条树枝，其他都为弦。例如，对于图7 -40(a) 所示图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]有一棵生成树[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex] 如图7 - 40(b) 所示，对应于的基本回路如图7 - 40(c) , (d) ， (e) 和(f) 所示，对应于[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]的基本割集如图7 - 40(g) , (h) ，(i)和(j) 所示。[img=940x520]1786902253c37fc.png[/img]我们有以下结论:(a) 一个割集和一个回路都有偶数条公共边;(b) 对给定一棵生成树[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]，设[tex=7.714x1.357]3mwijfr5Upc2DeKdiMDYD+Se+pzCFQyu/bjDZ8wkJsqQ+mAsxFo4SSgG8ID8n3G4[/tex]是一个基本割集，其中[tex=0.857x1.0]ibwbW1aAI4XVPcvOWmgM1g==[/tex]是[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]的树枝，[tex=3.857x1.0]fbU5xi67f7LFzfwSzDSnaqxTMSFmaQ1qp5E2F9C4ICg=[/tex]是[tex=0.643x1.0]awBC2UvU2WxG45VihksPuw==[/tex]的弦。那么[tex=0.857x1.0]+/XTNGLzGPyngtJjJYXZsQ==[/tex]包含在[tex=4.429x1.357]4tuOu0lb/oAocdI0olsdzObwBz9Gn0MmyYcL2Gj7yHeNUAi7fXvZCHPMUa3Khwz8[/tex]与对应的基本回路中。(a) 删去割集中所有边，把图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]分成两个彼此不相连通的子图[tex=1.143x1.214]tVkSXDTbP2YDKnpeqXNXXg==[/tex]和[tex=1.143x1.214]z/iyGGP+DXie1qfllHTsVg==[/tex]。[tex=1.143x1.214]tVkSXDTbP2YDKnpeqXNXXg==[/tex]与[tex=1.143x1.214]z/iyGGP+DXie1qfllHTsVg==[/tex]间连通的边都在割集中，从任一个结点出发又回到自身的回路必然在[tex=1.143x1.214]tVkSXDTbP2YDKnpeqXNXXg==[/tex]与[tex=1.143x1.214]z/iyGGP+DXie1qfllHTsVg==[/tex]之间来回偶数次（来回次数为0 ，表示此回路的所有结点都在[tex=1.143x1.214]tVkSXDTbP2YDKnpeqXNXXg==[/tex]或[tex=1.143x1.214]z/iyGGP+DXie1qfllHTsVg==[/tex]中) ，也就是说，此回路与割集有偶数条公共边。( b) 设[tex=0.714x1.0]J/aA9EEo0KmJFnWWfX7LmQ==[/tex]是对应于弦[tex=0.857x1.0]WHzaWG/tyfL26av1P4tQ8w==[/tex]的基本回路。因为[tex=0.857x1.0]WHzaWG/tyfL26av1P4tQ8w==[/tex]在[tex=0.714x1.0]J/aA9EEo0KmJFnWWfX7LmQ==[/tex]中，也在[tex=0.857x1.0]m2DKAQtGuc1DyN3zyNlILg==[/tex]中，由(a) 可知，[tex=0.714x1.0]J/aA9EEo0KmJFnWWfX7LmQ==[/tex]与[tex=0.857x1.0]m2DKAQtGuc1DyN3zyNlILg==[/tex]应有偶数条公共边，由于[tex=0.714x1.0]J/aA9EEo0KmJFnWWfX7LmQ==[/tex]中只有一条弦，即[tex=0.857x1.0]WHzaWG/tyfL26av1P4tQ8w==[/tex]， [tex=0.714x1.0]J/aA9EEo0KmJFnWWfX7LmQ==[/tex]与[tex=0.857x1.0]m2DKAQtGuc1DyN3zyNlILg==[/tex]公共边只能是树校，因此只可能[tex=0.857x1.0]+/XTNGLzGPyngtJjJYXZsQ==[/tex]为公共边。对应于[tex=3.857x1.0]zk5MYtUEyRrHZBKhTTqvYQq5xN3VvSKjwdNVV5CcA1c=[/tex]的基本回路中也包含[tex=0.857x1.0]+/XTNGLzGPyngtJjJYXZsQ==[/tex]，可类似证明。设[tex=1.071x1.143]ECyhF63nBaIW3dAmfbuEPg==[/tex]是这样的一个基本回路:它对应于不在[tex=0.857x1.0]m2DKAQtGuc1DyN3zyNlILg==[/tex]中的任何弦， [tex=1.071x1.143]ECyhF63nBaIW3dAmfbuEPg==[/tex]不能包含[tex=0.857x1.0]+/XTNGLzGPyngtJjJYXZsQ==[/tex]，因为否则[tex=1.071x1.143]ECyhF63nBaIW3dAmfbuEPg==[/tex]与[tex=0.857x1.0]m2DKAQtGuc1DyN3zyNlILg==[/tex]只有一条公共边[tex=0.857x1.0]+/XTNGLzGPyngtJjJYXZsQ==[/tex]， 这不可能。有了( a) 和（b)结果，就可以证明本题。边[tex=0.571x0.786]c59+3vo0/Vn/FvNRhDRu5g==[/tex]在[tex=1.0x1.214]W9y/AChQ6cjPFh4mePUysQ==[/tex]中，它是[tex=1.0x1.214]W9y/AChQ6cjPFh4mePUysQ==[/tex]的校，通过[tex=0.571x0.786]c59+3vo0/Vn/FvNRhDRu5g==[/tex]只有一基本割集[tex=0.857x1.0]m2DKAQtGuc1DyN3zyNlILg==[/tex]，边[tex=0.571x0.786]c59+3vo0/Vn/FvNRhDRu5g==[/tex]不在[tex=1.0x1.214]zUvLEpcJP27MfHQYIgGtCA==[/tex]中，它是[tex=1.0x1.214]zUvLEpcJP27MfHQYIgGtCA==[/tex]的弦，存在对应于边[tex=0.571x0.786]c59+3vo0/Vn/FvNRhDRu5g==[/tex]的基本回路[tex=0.714x1.0]J/aA9EEo0KmJFnWWfX7LmQ==[/tex]，割集[tex=0.857x1.0]m2DKAQtGuc1DyN3zyNlILg==[/tex]与回路[tex=0.714x1.0]J/aA9EEo0KmJFnWWfX7LmQ==[/tex]有公共边[tex=0.571x0.786]c59+3vo0/Vn/FvNRhDRu5g==[/tex]， 由( a)可知，它们至少还有一条公共边[tex=0.429x1.0]JThLUuJ8WswSAPiYZWihWg==[/tex]。由于[tex=0.429x1.0]JThLUuJ8WswSAPiYZWihWg==[/tex]在基本回路[tex=0.714x1.0]J/aA9EEo0KmJFnWWfX7LmQ==[/tex]中，[tex=0.429x1.0]JThLUuJ8WswSAPiYZWihWg==[/tex]是[tex=1.0x1.214]zUvLEpcJP27MfHQYIgGtCA==[/tex]的枝，又[tex=0.429x1.0]JThLUuJ8WswSAPiYZWihWg==[/tex]在基本割集[tex=0.857x1.0]m2DKAQtGuc1DyN3zyNlILg==[/tex]中，[tex=0.429x1.0]JThLUuJ8WswSAPiYZWihWg==[/tex]不是[tex=1.0x1.214]W9y/AChQ6cjPFh4mePUysQ==[/tex]的校。在树[tex=1.0x1.214]zUvLEpcJP27MfHQYIgGtCA==[/tex]中，删去边[tex=0.429x1.0]JThLUuJ8WswSAPiYZWihWg==[/tex]， 加上边[tex=0.571x0.786]c59+3vo0/Vn/FvNRhDRu5g==[/tex]，可得到图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的一棵生成树，由此可得:[tex=6.571x1.357]+ZCN2vaQzLIPSHQnzuX8BKTPUhEeBLFOTeYoaTxvd+ubjKV+M8P7kNZJXXEqqRdh[/tex]是图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的生成树。由于[tex=0.429x1.0]JThLUuJ8WswSAPiYZWihWg==[/tex]在基本割集[tex=0.857x1.0]m2DKAQtGuc1DyN3zyNlILg==[/tex] 中，边[tex=0.571x0.786]c59+3vo0/Vn/FvNRhDRu5g==[/tex]是[tex=0.857x1.0]m2DKAQtGuc1DyN3zyNlILg==[/tex]中的枝，由(b) 可知， [tex=0.571x0.786]c59+3vo0/Vn/FvNRhDRu5g==[/tex]包含在对应边[tex=0.429x1.0]JThLUuJ8WswSAPiYZWihWg==[/tex]的基本回路中，因此删去边[tex=0.571x0.786]c59+3vo0/Vn/FvNRhDRu5g==[/tex]而添加边[tex=0.429x1.0]JThLUuJ8WswSAPiYZWihWg==[/tex]， 即[tex=6.571x1.357]Kkk1veYVxj+Z+62ASdcq0/BGz98DsPM3ECZ8+A6kAjBfNhrQwMvg07vgSe/k99ra[/tex]也是图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的一棵生成树。