由于C是G的生成子图,G一般比C有更多的边,或者说G比C有更强的连通性,即
,故结论成立.
由定理可知,有割点的图一定不是汉密尔顿图.这是因为若v是图G的割点,则
.
例如,图8-24中的G2
不是汉密尔顿图,因为
.
此定理是必要但不是充分的,这就是说,即使
成立也可能不是汉密尔顿图.例如,图8-24中的G3
就满足此条件,但它不是汉密尔顿图.此图称为"彼得森(Petersen)图".
[延伸]
与中国邮路问题类似,在一个网络中经常要计算哪条汉密尔顿路是最短的,这样的问题称为"巡回售货员"问题或"货郎担"问题[48
]
.
[延伸]
无论是欧拉路还是汉密尔顿路,并非不存在求解算法.例如,可以将所有边或结点进行全排列