设G= 为连通图,且e∈E。证明:当且仅当e是G的割边时,e才在G的每棵生成树中。

设G= 为连通图,且e∈E。证明:当且仅当e是G的割边时,e才在G的每棵生成树中。
【正确答案】：证明:G= ,设e=(u,v)∈E
 充分性 e是G的割边,反证,若存在某MST T1,e ∉T1,在T1中,u与v之间可达,在(G-{e})中,u与v之间仍可达,则e不是G的割边。矛盾。
 必要性 e存在于G的每棵生成树中。若e不是G的割边,则G1=(G-{e})仍是连通的,G1的生成树T显然也是G的生成树,但e ∉T,矛盾。