(③)如果n阶单图G度优于所有的Cmn图族，则G 是H图。 例如： G G的度序列是(2,3,3,4,4)，优于C1.s的度序列 (1,3,3,3,4)和C2.s的度序列(2,2,2,4,4)。所以可以断 定G是H图。 推论设G是n阶单图。若n≥3且 E(G)
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 (3) 如果n阶单图G度优于所有的Cm,n图族，则G 是H图。 G的度序列是(2,3,3,4,4),优于C1,5的度序列 (1,3,3,3,4)和C2,5的度序列 (2,2,2,4,4)。所以可以断 定G是H图。 例如： G 推论 设G是n阶单图。若n≧3且 1 ( ) 1 2 n E G − +
则G是H图；并且，具有个顶点 ”2 条边 的非H图只有C1.n以及C2.5 证明：(1)先证明G是H图。 若不然，由定理1，G度弱于某个Cm,于是有： EGE(C=m+(n-2m(n-m-D+m(m-D ("2）1-m-m-2》-om-Xn-2m- 这与条件矛盾！所以G是H图
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 则G是H图；并且，具有n个顶点 条边 的非H图只有C1,n以及C2,5. 1 1 2 n − + 证明: (1) 先证明G是H图。 若不然，由定理1，G度弱于某个Cm,n,于是有： 2 , 1 ( ) ( ) ( 2 )( 1) ( 1) 2 1 1 1 ( 1)( 2) ( 1)( 2 1) 2 2 1 1. 2 E G E C m n m n m m m m n n m m m n m n = + − − − + − − = + − − − − − − − − + 这与条件矛盾！所以G是H图
(2)对于C1m,有： (G)=C)= +1 除此之外，只有当m=2且n=5时有： 16G=l6c》-（"2+1 这就证明了(2)。 注：推论的条件是充分而非必要的
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 (2) 对于C1,n,有： 除此之外，只有当m=2且n=5时有： 1, 1 ( ) ( ) 1. 2 n n E G E C − = = + 这就证明了(2)。 , 1 ( ) ( ) 1. 2 m n n E G E C − = = + 注：推论的条件是充分而非必要的
例如，在下图中，尽管C2,+v的边数不满足推 论不等式，可它是H图。 C2.7+uv
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 例如，在下图中，尽管C2,7+uv的边数不满足推 论不等式，可它是H图。 u v C2,7+uv
例1设G是度序列为(d1,d2,dn)的非平凡单图，且 d1≤d2≤.≤dn。证明：若G不存在小于(m+1)/2的正 整数m,使得：dm<m且dnm+1<n-m,则G有H路。 证明：在G之外加上一个新点v,把它和G的其余各 点连接得图G1 G G的度序列为：(d1+1,d2+1,dn+1,n) 由条件：不存在小于(m+1)/2的正整数m,使得 dm十1≤m,且dn*+1<n-+1=(n+1)-m。于是由度序列 判定定理知：G是H图，得G有H路
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 例1 设G是度序列为(d1 ,d2 ,.,dn )的非平凡单图，且 d1≦d2≦.≦dn。证明：若G不存在小于(n+1)/2的正 整数m，使得：dm<m且dn-m+1<n-m,则G有H路。 证明：在G之外加上一个新点v,把它和G的其余各 点连接得图G1 G G1 v G1的度序列为：(d1+1,d2+1,.,dn+1, n) 由条件：不存在小于(n+1)/2的正整数m,使得 dm+1≦m,且dn-m+1+1<n-m+1=(n+1)-m。于是由度序列 判定定理知：G1是H图，得G有H路