赋权图中存在重圈的一个定理的新证明

摘要

给出了如下定理的一个新的简短的证明:若G是一个满足k≥2的k连通赋权图,则G或者包含一个权至少为2m/(k+1)的圈,或者包含一个Hamilton圈,如果以下条件成立:(1)任意k+1个相互独立的顶点的赋权度和至少为m;(2)在G的每个导出爪,导出修正爪和导出P4中,所有边的权都相等.