问答题
证明:当且仅当G的一条边e不包含在G的回路中时,e才是G的割边.
【正确答案】(必要性)设e是连通图G的割边,e关联的两个结点是u和v.如果e包含在G的一个回路中,那么除边e=(u,v)外,还有一条分别以u和v为端点的路,所以删去边e后,G仍为连通图,这与e是割边相矛盾.
(充分性)如果边e不包含在G的任一回路中,那么连接结点u和v只有边e,而不会有其他连接u和v的任何路.因为如果连接u和v还有不同于边e的路,此路与边e就组成一条包含边e的回路,从而导致矛盾.所以删去边e后,u和v就不连通,故边e是割边.
【答案解析】