电子科技大学：《图论及其应用 Graph Theory and its Applications》研究生课程教学资源（课件讲稿）14 度极大非哈密尔顿图与TSP问题

(3)如果n阶单图G度优于所有的Cmn图族，则G 是H图。 例如： G G的度序列是(2,3,3,4,4)，优于C1s的度序列 (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 7 (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图只有C1n以及C2.5 证明：(1)先证明G是H图。 若不然，由定理1，G度弱于某个Cm,于是有： E(G川≤E(C.=[m2+(n-2m)(n-m-1)+m(n-1)] （”21-安(m-1Xm-2y-m-10a-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 8 则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 EG EC m n m n m mn m n n m m m nm n                                   这与条件矛盾！所以G是H图