本文考虑的图若无特殊声明均为简单、无向有限图,对于一个图G=G(V(G),E(G)),我们用V(G)和E(G)分别表示图的顶点集合和边集合。对任意的v∈V(G),我们用d_G(v)表示顶点v在G中的度数。Δ(G)和δ(G)分别表示图G的最大度和最小度,对V(G)的子集S,用G-S表示从G中删去顶点集合S及其关联的边所得到的子图。若S={v},则令G-v=G-{v}。对E(G)的子集X,用G-X表示从G中删去边集合X所得的子图,若X={e},则G-{e}简记为G-e。若存在V(G)的两个不交子集X、Y,使得V(G)=X∪Y,且G的所有边均一个端点在X内,另一个端点在Y内,则称G为二部图,记为G=(X,Y,E(G))。如果|X|=|Y|,则称G为均衡二部图。　　设g和f是定义在V(G)上的两个整数值函数,使对任意的v∈V(G)有0≤g(v)≤f(v)。若H是图G的一个支撑子图,且满足对任意顶点v∈V(H),g(v)≤d_H(v)≤f(v),那么我们就称H是图G的一个(g,f)-因子。如果对任意的v∈V(H)有g(v)=a、f(v)=b,则称G的(g,f)-因子为[a,b]-因子。若a=b=k,则此时称[a,b]-因子为k-因子,k=1时也称1-因子为完美对集。对于图G的一个因子,如果它同时包含G的一个哈密顿圈,我们就称该因子为G的一个哈密顿因子。图G的顶点数|V(G)|我们通常称为G的阶,一般用n来表示。如果图G的最小度δ(G)≥n/2,但对于G的任意一条边e,δ(G-e)