(二)、性质与判定 1、性质 定理1（必要条件）若G为H图，则对V(G)的任一非空 顶点子集S,有： o(G-S)≤lS 证明：G是H图，设C是G的H圈。则对V(G)的任意 非空子集S,容易知道： o(C-S)≤lS到 所以，有： o(G-S)≤o(C-S)≤S
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 (二)、性质与判定 1、性质 定理1 (必要条件) 若G为H图，则对V(G)的任一非空 顶点子集S，有： ( ) GS S 证明：G是H图，设C是G的H圈。则对V(G)的任意 非空子集S, 容易知道: ( ) CS S 所以，有： ( )( ) GS CS S
注：不等式为G是H图的必要条件，即不等式不满足 时，可断定对应图是非H图。 例3求证下图是非H图。 G 证明：取S={2,7,6},则有：o(G-S)=4>S=3 所以由定理1知，G为非H图。 8
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图的必要条件，即不等式不满足 时，可断定对应图是非H图。 例3 求证下图是非H图。 证明：取S=｛2, 7, 6｝,则有： 4 5 3 2 1 8 7 6 9 ( )4 3 GS S 所以由定理1知，G为非H图。 G
注意：满足定理1不等式的图不一定是H图。 例如：著名的彼德森图是非H图，但它满足定理1的 不等式。 Peterson图 彼得森(1839--1910)，丹麦哥本哈根大学数学教授。 家境贫寒，因此而辍过学。但19岁就出版了关于对数的 专著。他作过中学教师，32岁获哥本哈根大学数学博士 学位，然后一直在该大学作数学教授
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 注意：满足定理1不等式的图不一定是H图。 例如：著名的彼德森图是非H图，但它满足定理1的 不等式。 Peterson图 彼得森(1839----1910)，丹麦哥本哈根大学数学教授。 家境贫寒，因此而辍过学。但19岁就出版了关于对数的 专著。他作过中学教师，32岁获哥本哈根大学数学博士 学位，然后一直在该大学作数学教授
彼得森是一位出色的名教师。他讲课遇到推理困难时， 总是说：“这是显而易见的”，并让学生自己查阅他的著 作。同时，他是一位有经验的作家，论述问题很形象，讲 究形式的优雅。 1891年，彼得森发表了一篇奠定他图论历史地位的长达 28页的论文。这篇文章被公认是第一篇包含图论基本结论 的文章。同时也是第一次在文章中使用“图”术语。 1898年，彼得森又发表了一篇只有3页的论文，在这篇文 章中，为举反例构造了著名的彼得森图。 10
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 彼得森是一位出色的名教师。他讲课遇到推理困难时， 总是说：“这是显而易见的”，并让学生自己查阅他的著 作。同时，他是一位有经验的作家，论述问题很形象，讲 究形式的优雅。 1891年，彼得森发表了一篇奠定他图论历史地位的长达 28页的论文。这篇文章被公认是第一篇包含图论基本结论 的文章。同时也是第一次在文章中使用“图”术语。 1898年，彼得森又发表了一篇只有3页的论文，在这篇文 章中，为举反例构造了著名的彼得森图