当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的一条边[tex=0.5x0.786]WKYr2kz69xrVCyPvbyVG1w==[/tex]不包含在[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的闭迹中时，[tex=0.5x0.786]WKYr2kz69xrVCyPvbyVG1w==[/tex]才是[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的割边。
举一反三
- 证明:简单图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是二分图，当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]没有包含奇数条边的回路。
- 设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是带有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的简单图。证明：[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是树当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]没有简单回路并且有[tex=1.929x1.143]odTH0p5clPZMk1jQf4ctjw==[/tex]条边。
- 设[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是带有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点的简单图。证明：[br][/br][tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是树当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是连通的并且有[tex=1.929x1.143]odTH0p5clPZMk1jQf4ctjw==[/tex]条边。
- [tex=0.643x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的顶点数大于[tex=0.5x1.0]/BQKP5E8YnupUQ2sDg7w1Q==[/tex]且[tex=1.571x1.0]yFMW7iKbDUvC9rxmlgBbDQ==[/tex]属于[tex=2.143x1.0]cfyQS3UGXbUlYs40wDhTjQ==[/tex]不相邻，且满足[tex=5.857x1.357]7V7Bn55kw9+tF7TAU7CTXi60Ac6nyTVGpTHP6zf/aUQ=[/tex]，证明:[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]为Hamilton 图当且仅当[tex=2.071x1.143]Fl+QzjOjSLXVNyOw2d/fHg==[/tex]为Hamilton 图，[tex=0.5x0.786]WKYr2kz69xrVCyPvbyVG1w==[/tex]为[tex=1.571x1.0]yFMW7iKbDUvC9rxmlgBbDQ==[/tex]新边。
- 证明:若[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是连通图，则有可能删除顶点使[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]变成不连通的当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]不是完全图。