哈密顿联通问题求证：若图G是哈密顿联通的,且顶点数n>=4,则边数e>=(3n+1)/2哈密顿联通的意思是任何两点有哈密顿路1L....你画个图看看

Question

哈密顿联通问题
求证：若图G是哈密顿联通的,且顶点数n>=4,则边数e>=(3n+1)/2
哈密顿联通的意思是任何两点有哈密顿路
1L ....你画个图看看

Answer 1

证明 如果图G是哈密顿联通的,则G中所有点的度数均不小于3,显然G中所有点的度数均大于等于2,如果有一个点w度数小于2,则连结任意两个其它点的路不可能过w,如果有一点w度数等于2,设与其相邻的点是u和v.由于n≥4,必然还有另外的点w'也在图G中,则由u到v的基本路,如果经过w,u-w-v,就不可能再经过w',故u到v不存在哈密顿路.
由所有点的度数均不小于3,故得 2e≥3n,边数e≥3n/2,如果n是偶数,则e≥3n/2= [(3n+1)/2];
如果n是奇数,由于图中不能有奇数个奇数度结点,故至少有一个点度数不小于4,故2e≥3(n-1)+4=3n+1,e≥(3n+1)/2,e≥[(3n+1)/2].