图G无向连通图,G中有割点或桥,则无汉密尔顿图,怎么证明如题就是证明这条定理,不用图 请问lca001,为什么连结桥的两个结点必有一个结点是割点?
问题描述：
图G无向连通图,G中有割点或桥,则无汉密尔顿图,怎么证明
如题
就是证明这条定理,不用图
请问lca001,为什么连结桥的两个结点必有一个结点是割点?
答
首先证明G中有割点,则G不是汉密尔顿图,反证法,如果图G是汉密尔顿图,则必存在汉密尔顿圈(回路),即所有结点均在一个回路中,此时删除任意一个结点图G必连通,于是它的任何点均不是割点,矛盾,即有割点的图不是汉密尔顿图....