下面是改进宋,增民理事长等权威的邻域并的代表性工作（宋,增民教授九十年代已是东南大学学报主编，科教大省江苏省数学学会理事长，现是江苏省工业与应用数学学会理事长，他的秘书长是该东南大学工会委员会主席管平教授

关于邻域并-虽我们海南山区90年代初已居于世界领先-可仍一直没有分文经费，其它方面也非常无奈。要知最下面见邻域并中国第一人兼江苏省(世界知名大学数量江苏省超过北京成为中国第一)省工业与应用数学学会第3和第4届正理事长宋增民教授当时说“世界上邻域并做得最好的是海南”（该校邻域并很强:这里第(1)的留校的邻域并专家尹家洪、下面1991年南京大学大会的邻域并作者贾彪,以及南京师大的邻域并专家朱卓宇,和邻域并第一人宋增民理事长都是同班同学，这南京大学大会的这篇邻域并作者赵俊也和宋理事长同单位-不过第一作者是1934年生的东北大学田永程--这大会上当时强大的东北大学还有赵宝泽和同年龄的党恺谦2个中坚教授各独立写一篇-不过其后沈阳经济都不如大连等。当时,邻域并主要用于研究单圈和复圈结构图--单圈非常简单-一出就易找到方法解决-而关于复圈结构图-那可是包含除单圈的哈密顿圈外的齐次可迹、哈密顿连通图、(无参数的2百页的泛圈图//有参数的泛圈图)、点泛圈图、边泛圈图、泛连通图、最短路泛圈等8领域16个小领域--并如这里见世界首富比尔·盖茨的唯一科学论文就做哈密顿图/世界第一企业谷歌也基于图论及哈密顿图--要知之不易如这里第2段见仅一个泛圈图领域就足够名家们写一部专著和花半生去钻探它-而邻域并的这全部领域都是海南琼大最先突破/此外其它重要条件如最小度/度和/范型等也再获进展居世界领先。关于宋理事长的这学会-刚见这页第一段的中国第一科学家曹进德院士成为宋增民理事长之后的第7届正理事长。宋教授当时主持一个在国内外都有影响的强大的哈密顿图国家级科研团队-他的学生许多也已成本领域世界级专家如刚见宋增民教授推荐去香港大学读博的他的研究生陈旭瑾教授都已是全国图论组合学会副理事长、全国博弈论学会副理事长(副主任委员)、最近还任全国数学规划分会副理事长并兼实际掌管的秘书长-对这个学会不了解但排在她前面的陈小君教授是香港理工大学应用数学系主任(只是没有见到陈旭瑾教授的学位论文-不过见到其他一些如宋教授指导的2013年已见是华东师范大学数学系系副主任吕长虹的研究生学位论文[2017年才由数学系改为数学学院并有50个教授且副教授中也有8人是博士生导师])。关于邻域并-先是欧美基于分析综合拓展以前各类先进优化条件的基础上深化综合发展构建之-就象这里第2段见国家基金委仍唯一只怀抱着它-也实没其它办法-要知80/90年代世界各国对它迷信到风起云涌-以为是这世界最悠久的哈密顿性重大难题的天梯似显曙光。这里最后段见其中的点泛圈领域的一个很小部分-偶图做了一辈才仅做到8。不仅偶图还可能要做几辈子，而点泛圈还有立方体、平面、无爪等等各特殊图呢。复圈结构图的上面其它各领域的偶图、立方体、平面等等特殊图呢。虽然我也完成了偶图立方体、无爪、平面图等很多前瞻性研究工作，但其实，世界各国大师权威们更关注把所有特殊图即偶图、立方体等一般化了的非常不容易的一般图-这才登高统观全局，就象我最近在国家基金中说的以美法德英等欧美多国在八十年代更投入以校长主席等为首的圈图的主力部队研究之并提出猜想，但世界各国在1998年前在复圈结构图任何一个领域都没有取得一点突破，而琼州大学在1993年前就不只突破而是彻底完成一般图的复圈结构图的上面哈连通图、泛圈图、点泛圈、边泛圈、泛连通等全部领域）。当时我在电话里问宋教授时因是新人就没有报上我的名，而当我听到宋教授如此评价时，大为震惊--要知道我当时在邻域并的复圈结构图全部领域就只做这一篇-它是我1991年前完成的论文-而且以后各篇比它难得多-更使人望而生畏--但仅这非常简单的一篇就被认为在汪洋大海般广阔的复圈结构图做得最好-怎不震惊--它证明美国5个权威大师1985年在大会提出的这里的点泛圈猜想--这个猜想的界NC+δ³n+1更不如我这篇海南大学的NC+δ³n难于突破-世界各地都象爬在地上攀珠峰之每一步都艰巨、更不如比它更早完成的这里几篇艰难、也不如我这里百篇艰难、甚至n+1啊可能都不如在它之前完成的这十几篇还艰难…-而且全世界都清楚地知道若解决这个点泛圈猜想将也许有可能使上面近十个领域的突破迎来星星点点或各不同程度的曙光（确实，我其后在1993年前就解决完成全部这近十个领域几十篇论文-而它们每一篇都比上面点泛圈猜想这篇难上不只几个层次-且所用方法技术等都没有多少不同的--其拚命才具决定性）--可就使如此明确然而世界各地就是对n+1这么简单的点泛圈猜想却都一直束手无策---必竟世界权威们也在国内外会议和杂志都公报这猜想但这么多年都毫无一点进展也找不到解决的头绪！！！我如此震惊还基于2点：第1、包含哈密顿图的复圈结构图是已有一千多年的世界最悠久的世界艰巨问题（陈景润先生的哥德巴赫猜想才仅有300年，当然哈密顿图的突破非常艰难进展非常缓慢非常小不如陈景润的，也许一千年后仍不如陈景润的）；第2、1985年以前研究这世界最悠久领域的最好条件是“最小度”和“度和”，而邻域并是推广包含它俩的，可见这震惊…。宋教授这样评价也许基于2点：第1、1998年以前全世界在邻域并的复圈结构图取得突破的论文只有我这篇；第2、其后的复圈结构图的其它领域照搬我这篇的方法就可以完成所有领域的工作-所以不要小看一篇论文。要知宋教授九十年代已担任东南大学学报主编、东南大学出版社社长、东南大学党委委员、江苏省新闻与出版协会副主席等(这大学改来改去不是很了解但见“北大以文史哲著称,东南大学以科学名世”--是否曾是“国立中央大学”之缘-但也过于夸吧只是应也不错，并该校出版社在宋教授仍在任的2007年是全国首批18家重要大学出版社之一)。宋教授九十年代也已是哈密顿图世界权威，如美国十大老牌大学学术委员会主席Gould大师撰写的世界最权威哈密顿图综述论文引用的宋增民理事长的论文是我国大陆专家中最多的-这综述论文不仅是21世纪以前最全面的而且也可能是至今最有影响最著名的综述-当然新结果不断出现肯定已不全面（可这不仅海南五指山在“邻域并”的各类复圈结构图都是世界上最先突破的，而且以前在“最小度”、“度和” 、“范型”以及推广它们的条件对长圈/可迹/哈密顿圈和各类复圈结构图的研究上我也在世界各国已攀登上的最好高峰上再做某些最好可能的进一步前进,以及“现代计算机之父”和“计算机之母”的导师推动的“k路哈密顿图”以及这里第9节为主等相关领域的“Hypo-Hamiltonian、k-ordered哈密顿性、控制圈、G可圈、S点集-可圈、k点数-可圈、cycle extendability、S-pancyclable、set-pancyclic 、subpancyclic、k-semipancyclic、k-path Hamiltonian、S-locally pancyclic、pan-k-linked graphs、k不交圈、F-哈密顿图(F是独立边集) 及G×K₂的Prism 哈密顿性”，还有在图论的荫度、图着色、生成树，教育部审定通过的中国‘第一本’数学研究生用书“组合矩阵论”，“极值集合论”，“化学分子轨道图形理论”，“图的连通性”等等等--都取得世界先进水平的进展，可见,以前…）

关于宋教授的权威，也如在南京大学召开的1991年首届全国哈密顿图大会的论文集（《南京大学学报》第27卷出版）中田丰老师和张莲珠教授合写的“哈密顿图综述文章”引用宋增民教授的第一作者论文4篇是全国专家中最多的；而这图论排名全世界第25的张克民教授为这大会撰写的另一篇“哈密顿图综述文章”引用宋增民教授的第一作者论文11篇是全世界专家中最多的，其次是刚在1990年的国际数学家大会做45分钟报告的Thomassen院士的10篇）。可惜的是宋增民教授1999年再进一步出任东南大学出版社社长后因要一定程度自负盈亏社内百号员工就得等着他带领创收那就得全身心考虑赚钱等 (宋增民教授不仅撰写被这1991年大会多篇论文引用的《图论与网络最优化》一书，还因图论在管理科学也有重要应用及因他是多方面领导，宋增民教授在1987年也已出版的《管理的图论方法》专著也很有名，这是他学术和管理互相促进的杰作结晶，宋增民教授九十年代初已是东南大学学报主编(以前一些学报主编是校长兼任的)、九十年代末起至今也已担任第3届和第4届江苏省工业与应用数学学会理事长（他当社长的出版社在2006年已成为全国12家销售过5亿元的出版社之一，这在当时是很不错的、很吸引人的-这让他看到这方面超过全国同行业领袖的才能-这也许是促使他其后更专注于…）。做为科教大省的江苏省的该学会在全国居重要地位。宋增民理事长的秘书长管平教授此时是宋教授的大学的工会主席（这可是最清楚宋教授资格的。工会主席许多是副校领导兼，管平此时也和校领导委员-校纪委副书记并列，管平也是华东六省高等数学研究会理事长），象这个科教大省的李刚、曹德欣、田立新、刘祖汉、周汝光、秦士嘉、秦志林等这些都是国家重点大学副校长、省级大学正副校长以及还有许多国家名师五一奖章杨孝平等都出任宋增民理事长的这2届时的这个学会的副理事长或常务理事（这些大学校长也都是著名数学专家），其它常务理事也很突出如肖伟教授是有近万员工的国家重点高新技术企业董事长全国人大代表。可见宋增民教授的学会的级别非常权威、宋教授也是值得推崇)。宋增民教授1990年编著出版的《图论》著作一直被许多大学做为我国自编的主要教材。如宋教授出任江苏省版协副主席--八个副主席中只有宋教授来自大学--一个副主席是省新闻局前正局长排在宋教授后面的也是江苏省新闻局副局长。如此这里倒数第12行见宋增民理事长再被委任为北京市最大的综合性出版机构、国家七家试点出版集团之一的北京出版社出版集团总经理…。也如他调上北京市后的江苏省副主席被免去，而增补的重点大学-中国矿业大学出版社社长仅为理事、接替他的来自他的大学的也仅是常务理事。此外，胸怀大志的宋理事长还注册3000万元成立北京凤凰天下文化发展有限公司自任董事长并已出版很多高水平的珍稀的图书，还如产生很多院士的全国百强县区榜单占了5项的他的家乡姜堰的第1个现代科技企业姜堰市晨光印刷有限公司也是他的等等-这个政府网公告找不到了可看百度)。转型如此成功，真是了不起非常不简单的一个书生！也许是他抱负很大而又不看到当厅长校长省长等需要太黑暗的手段吧,而且该当的他都已当过了,如此倒不如以实业发展自已也还尚能发展国家吧，因此很遗憾这使中国失去了一个领军性的科学家，世界也失去已崭露国际影响力的准世界级权威。众所周知哈密顿图问题是已有一千多年世界最悠久并被公认居图学世界三大难题之首的问题，如此一个多世纪以来一代又一代世界各国数学家为之奋斗不息，而近二十年来备受世界各国最重视和最推崇的“邻域并”条件就是在综合、发展和改进以前所有条件的基础上由五个美国大学校长主席最先提出的-巴黎大学等权威也受到启发以类似形式提出，然而，九十年代初哈密顿图大师宋增民理事长在电话中竟对我说在“邻域并的复圈结构图各领域在世界上做得最好的是海南”--只可惜自我1993年来海南深山区后已不断地逐渐陷入很多艰难的困境，不论如何,因当时宋理事长绝对是邻域并中国第一人(如宋理事长和加拿大综合第一的西蒙大又在微软总部工作的秦在1990年左右合作的一些初步工作/还有这里做世界最艰巨进展的第(1)是我国最早的-并在1990年南京大学全国哈密顿大会最后的“问题研究”中邻域并问题由宋理事长来提)，如此这评价还是使我一直有些吃惊的（当时我是打电话问宋社长主编理事长的,那时电话还没有免提不会知道电话来自哪,我也只说我是研究图论多年的小大学无名讲师-他也不问我的名,我其中问到各国邻域并的各类高哈密顿图发展状况怎样-他说进展仍很难他并说做得最好的是海南-和他说国外在这些泛圈类的各类哈密顿图也尚没有很好的进展[他可能只看到/听到或审到我的部分论文-肯定不会了解我的全部-因我当时确实已在这所有8个邻域并领域16个小领域全部都已彻底突破]。因他是多个方面的领导而且抱负很大我就也不敢问得太多）

这里一直没有经费，很无奈，可下面这学科世界权威、第2和第3届江苏省工业与应用数学学会理事长宋增民教授当时说“邻域并的复圈结构图做得最好的是琼州大学”（复圈结构图包含哈连图、泛圈、点泛圈、边泛圈、泛连通等领域。而这里最后段见一个领域就够一辈头痛）。当时我在电话里问宋教授时因是新人就没有报上我的名，而当我听到宋教授如此评价时，大为震惊，因为我当时在邻域并的全部所有领域只做一篇-即我1991年前完成的论文--它是证明美国5个权威大师1985年在大会提出的点泛圈猜想-且这个猜想的界NC+δ³n+1比我这篇海南大学的NC+δ³n简单容易多了。我如此震惊还基于2点：第1、包含哈密顿图的复圈结构图是一千年以上的世界最悠久的问题；第2、1985年以前研究世界最悠久领域的最好条件是“最小度”和“度和”，而邻域并是推广包含它俩的，可见这震惊…。宋教授这样评价也许基于2点：第1、1998年以前全世界在邻域并的复圈结构图取得突破的论文只有我这篇；第2、其后的复圈结构图的其它领域照搬我这篇的方法就可以完成所有领域的工作-所以不要小看一篇论文。要知宋教授九十年代已是东南大学学报主编、东南大学出版社社长、东南大学党委委员、江苏省新闻与出版协会副主席等。宋教授九十年代也已是哈密顿图世界权威，如美国十大老牌大学学术委员会主席Gould大师撰写的世界最权威哈密顿图综述文章引用的宋增民理事长的论文是我国大陆被引用最多的

关于宋教授的权威，也如在南京大学召开的1991年首届全国哈密顿图大会的论文集（《南京大学学报》第27卷出版）中田丰老师和张莲珠教授合写的“哈密顿图综述文章”引用宋增民教授的第一作者论文4篇是全国专家中最多的；而这图论排名全世界第25的张克民教授为这大会撰写的另一篇“哈密顿图综述文章”引用宋增民教授的第一作者论文11篇是全世界专家中最多的，其次是刚在1990年的国际数学家大会做45分钟报告的Thomassen院士的10篇）。可惜的是宋增民教授1999年再进一步出任出版社社长后因要一定程度自负盈亏社内百号员工就得等着他带领创收那就得全身心考虑赚钱等 (图论也是在管理科学有重要应用的学科，如宋增民教授1987年已出版的《管理的图论方法》专著也很有名，这是他学术和管理互相促进的杰作结晶，宋增民教授九十年代初已是东南大学学报主编(以前一些学报主编是校长兼任的)、九十年代末起至今也已担任2届江苏省工业与应用数学学会理事长。做为科教大省的该学会在全国居重要地位。宋增民教授的学会秘书长管平教授是华东六省高等数学研究会理事长、也是宋教授的大学的工会主席（工会主席许多是副校长兼）。象李刚、曹德欣、田立新、刘汉祖、周汝光、杨孝平、秦士嘉、秦志林等多个重点大学和省级大学副校长都出任宋教授担任理事长的这2届时的这个学会的宋理事长的副理事长或常务理事。其它常务理事也突出如肖伟教授是有近万员工的国家重点高新技术企业董事长全国人大代表。所以宋增民教授的学会的级别非常权威）。宋增民教授1990年编著出版的《图论》著作一直被许多大学做为我国自编的主要教材。如宋教授出任江苏省版协副主席--八个副主席中只有宋教授来自大学--一个副主席是省新闻局前正局长排在宋教授后面的也是江苏省新闻局副局长。如此这里倒数第12行见宋增民理事长再被委任为北京市最大的综合性出版机构、国家七家试点出版集团之一的北京出版社出版集团总经理…。也如他调上北京市后的江苏省副主席被免去，而增补的重点大学-中国矿业大学出版社社长仅为理事、接替他的来自他的大学的也仅是常务理事。此外，胸怀大志的宋理事长还注册3000万元成立北京凤凰天下文化发展有限公司自任董事长并已出版很多高水平的珍稀的图书，他的家乡的第1个企业姜堰市晨光印刷有限公司也是他的等等)。转型如此成功，真是了不起非常不简单的一个书生！也许是他抱负很大而又不看到当厅长校长省长等需要太黑暗的手段吧,而且该当的他都已当过了,如此倒不如以实业发展自已也还尚能发展国家吧，因此很遗憾这使中国失去了一个领军性的科学家，世界也失去已崭露国际影响力的准世界级权威。众所周知哈密顿图问题被公认居三大难题之首，如此一个多世纪以来一代又一代世界各国数学家为之奋斗不息，而近二十年来备受世界各国最重视和最推崇的“邻域并”条件就是在综合、发展和改进以前所有条件的基础上由五个美国大学校长主席最先提出的-巴黎大学等权威也受到启发以类似形式提出，然而，九十年代初哈密顿图大师宋增民理事长在电话中竟对我说在“邻域并的复圈结构图做得最好的是琼州大学”，这一直使我吃惊？

A-1

宋增民教授的影响力，如姜益波的转让费达1600万的项目，他咨询数学家的这第15段见只特别专门拜访江苏省数学理事会会长、东南大学出版社社长宋增民教授求教。而一贯怀着实事求是作风的宋增民先生除了自已高瞻远瞩的的视野，他还为此专门向省内一些地区的数学教研员们详细了解了前景

宋增民教授的此邻域并的“哈密尔顿图”项目是该系最先获得国家教育部科技进步奖之一的项目照

我分别做出简单证明和改进的宋理事长的下面2个定理--它们是美国十大老牌大学学术委员会主席Gould大师撰写的世界公认的最权威哈密顿图综述文章引用的宋增民理事长的2篇论文的结果-即宋理事长只有2篇被引入Gould大师的这综述-但竟仍是我国大陆被这综述引用论文最多的专家（这2篇论文的结果在Gould的综述文章中分别列为定理40和定理44。其中宋理事长的这里前一篇6页的论文的定理40我在下面附件给出较简单证明-不过很遗憾因我们这里条件有限我还没有见到宋教授这论文-期望赠阅；这里第2篇更重要杂志上他和张克民教授合作的更重要的被上面综述收为定理44的更值得重视-如此我和Gould大师合作去推广发展它至顶峰-如此这里见要用12页才证完！）

哈密顿图权威大师、中国邻域并领域先导者宋增民理事长在90年代初曾说‘邻域并做得最好的是海南’（注:美国十大老牌名校的学术主席Gould大师撰写的世界公认的最权威哈密顿图综述文章共引用宋理事长2篇论文这也是我国大陆被引用最多的）。宋,增民教授九十年代初已是东南大学学报主编、江苏省数学学会理事长，现也已任多届江苏省工业与应用数学学会理事长，做为科教大省的该学会活动影响全国，他的学会秘书长管平教授是该东南大学工会委员会主席、校党委办公室主任。象李刚、曹德欣、刘汉祖、田立新、杨孝平、秦士嘉等该省众多重点大学副校长现都出任宋教授的这个学会的副理事长或常务理事）。宋,增民教授1990年编著出版的《图论》著作一直被许多大学做为我国自编的主要教材。在南京大学召开的1991年首届全国哈密顿图大会的论文集（《南京大学学报》第27卷出版）中田丰老师(这里第5页见他1979年已任中国图论学会秘书长-实际掌门人)和厦门大学博士导师张莲珠教授合写的“哈密顿图综述文章”引用宋增民教授的第一作者论文4篇是全国专家中最多的；而这世界第25的大师张克民教授为这大会撰写的另一篇“哈密顿图综述文章”引用宋增民教授的第一作者论文11篇是全世界专家中最多的，其次是1990年已在国际数学家大会做45分钟报告的Thomassen院士的10篇）。可惜的是宋增民教授1999年再进一步出任出版社社长后因要一定程度自负盈亏社内百号员工就得等着他带首养活那就得全身心考虑赚钱等 (图论也是在管理科学有重要应用的学科，如宋增民教授1987年已出版的《管理的图论方法》专著也很有名，这是他学术和管理互相促进的杰作，如宋理事长和江苏省新闻局长分别出任江苏省版协主席副主席-而象重点大学江苏大学和中国矿业大学社长等都仅被补为理事不是常务理事。如此这里倒数第12行见宋增民理事长再被委任为北京市最大的综合性出版机构、国家七家试点出版集团之一的北京出版社出版集团总经理…。此外，胸怀大志的宋理事长还注册3000万元成立北京凤凰天下文化发展有限公司自任董事长并已出版很多书，他的家乡的第一个企业姜堰市晨光印刷有限公司也是他的等等)。如此使中国失去了一个领军性的科学家，世界也失去已崭露国际影响力的准世界级权威。他的科研队伍、联盟以及研究生团队规模也缩小了，如在世界《图论网》见分来该数学系后一直受他指导、影响的该数学系博士导师林文松教授在纽约哥大《图论网》见他2002年以前来东大后的论文虽然不多但全是搞哈密顿图的邻域并，这是因哈密顿图非常不容易。该校一直受到宋理事长指导并留在该校的还有顾国华教授、吴建专教授、殷翔教授等等，宋,增民教授二十多年来还培养很多布遍国内外的专家如现在巴西巴拉那联邦大学的尹家洪教授、原在加拿大西蒙弗雷泽大学现在美国的秦升玉教授等等！他的科研队伍、联盟以及研究生团队规模也缩小了，如在世界《图论网》见分来该数学系后一直受他指导、影响的该数学系博士导师林文松教授在纽约哥大《图论网》见他2002年以前来东大后的论文虽然不多但全是搞哈密顿图的邻域并，足见哈密顿图非常不容易。该校一直受到宋理事长指导并留在该校的还有顾国华教授、吴建专教授、殷翔教授等等，宋,增民教授二十多年来还培养很多布遍国内外的专家如现在巴西巴拉那联邦大学的尹家洪教授、原在加拿大西蒙弗雷泽大学现在美国的秦升玉教授等等！众所周知哈密顿图问题是由牛顿之后的世界第一数学家于1856年提出并已是公认的图形学三大难题之一，也是在计算机、生物、化学、医学卫生统计以及城市规划等作用非常大、应用非常广的学科，如此一个半世纪以来一代代世界各国数学家为之奋斗不息，而近二十年来备受世界各国最重视和最推崇的“邻域并”条件就是在改进综合总结以前所有条件的基础上提出的。如此宋增民教授在上面1991年首届全国哈密顿图大会上提出的猜想中的邻域并猜想被我最先证明，也是全世界最先完成其它各类高哈密顿图的邻域并工作。如此九十年代初哈密顿图大师宋增民理事长在电话中对我说“邻域并的哈密顿图做得最好的是海南”一直使我吃惊？

Gould主席1991年的综述文章说“There are four fundamnetal results that I feel deservr special attention here—both for their contribution to the overall theory and for their affect on the development of the area. In many ways, these four results are the foundation of much of today’s work”即Gould主席说当今哈密顿图的大量工作依靠的两个结果是这里的定理1.1和定理1.2。在这综述中再说Reectly, a new “generalized degree”approach based upon neighborhood unions has proved to be useful.即1991年说推广“度型条件”的新条件“邻域并条件”已被证明是很有用的

Gould主席2003年的综述文章再说“I shall restrict attention in the this scetion to results involving size, degree, or neighborhood conditions. Degree conditions are the classic approach to hamiltonian problems and neighborhood unions are a form of generalized degree condition。即Gould主席说在综述中只概述哈密顿图的三个研究工具：“边数条件”“度型条件”和“邻域并条件”。而众所周知，“边数条件”往往被“度型条件”和“邻域并条件”包含而且它的应用不及“度型条件”和“邻域并条件”的1/8。

宋,增民教授的影响力，如姜益波的转让费达1600万的项目，他咨询数学家的这第15段见只特别专门拜访江苏省数学理事会会长、东南大学出版社社长宋增民教授求教。而一贯怀着实事求是作风的宋增民先生除了自已高瞻远瞩的的视野，他还为此专门向省内一些地区的数学教研员们详细了解了前景

宋,增民教授的此邻域并的“哈密尔顿图”项目是该系最先获得国家教育部科技进步奖之一的项目照

下面是琼州大学改进的宋增民理事长的哈密顿图的代表性工作（Gould主席撰写的世界公认的最权威哈密顿图综述文章共引用宋理事长的这篇论文和这篇论文-它们分别被我这里的定理[6]和定理[7]改进。2篇论文这也是我国大陆被引用最多的）。宋,增民教授九十年代初已是东南大学学报主编、江苏省数学学会理事长，现也已任多届江苏省工业与应用数学学会理事长，做为科教大省的该学会活动影响全国，他的学会秘书长管平教授是该东南大学工会委员会主席兼东南大学党委办公室主任。象李刚、曹德欣、刘汉祖、田立新、杨孝平、秦士嘉等众多重点大学副校长现在都任宋教授的这个学会的副理事长或常务理事）。宋,增民教授1990年编著出版的《图论》著作一直被许多大学做为我国自编的首选教材。在南京大学举办的1991年首届全国哈密顿图大会的论文集（《南京大学学报》出版）我国图论研究会秘书长田丰老师和厦门大学博士导师张莲珠教授撰写的《无向图的‘哈密顿图综述文章’》引用宋增民教授的第一作者论文4篇是国内专家中最多的；而这世界第25的大师张克民教授为这大会撰写的《有向图的‘哈密顿图综述文章’》引用宋增民教授的第一作者论文11篇在国内外专家中都是最多的，其次是1990年已在国际数学家大会做45分钟报告的Thomassen院士的10篇）。可惜的是宋增民教授1999年再进一步出任出版社社长后因要一定程度自负盈亏社内百号员工就得等着他来养活那就得全身心考虑赚钱等如此他不能再培养博硕士生否则这些员工意见就大了(图论也是管理科学化的一门学科，如宋增民教授1987年已出版的《管理的图论方法》专著也很有名，这是他学术和管理互相促进达到新高峰的写照，如宋理事长和20个教育部属社是中宣部部长刘云山发来贺信、中宣部常务副部长出席的中国版协理事之一，又如他和江苏省新闻局长也分别出任江苏省版协主席副主席-而象重点大学江苏大学和中国矿业大学社长等都不得常务理事仅被补为理事。如此这里倒数第12行见宋增民理事长再被委任为北京市最大的综合性出版机构、国家七家试点出版集团之一的北京出版社出版集团总经理…）。如此使中国失去了一个领军性的科学家，世界也失去已崭露国际影响力的准世界级权威。他的科研队伍、联盟以及研究生团队规模也缩小了，如在世界《图论网》见分来该数学系后一直受他指导、影响和帮助的该数学系博士导师林文松教授在《图论网》的15篇论文中2002年以前来东大后的论文虽然不多但全是搞哈密顿图的邻域并，足见哈密顿图非常不容易如此其后林教授转变研究方向。该校一直受到宋理事长指导并留在该校的还有顾国华教授、吴建专教授、殷翔教授等等，宋,增民教授二十多年来还培养很多布遍国内外的专家如现在巴西巴拉那联邦大学的尹家洪教授、原在加拿大西蒙弗雷泽大学现在美国的秦升玉教授还有中科院陈研究员等等，特别是宋教授在八十年代末及九十年代初培养的每一个硕博士真的都做得很不错！众所周知哈密顿图问题是由牛顿之后的世界第一数学家于1856年提出并已是公认的图形学三大难题之一，也是在计算机、生物、化学、医学卫生统计以及城市规划等作用非常大、应用非常广的学科，如此一个半世纪以来一代代世界各国数学家不断改进和完善其研究工具、条件和方法，而近二十年来受世界各国最重视和最推崇的“邻域并条件”就是在总结和改善以前所有条件的基础上由美国大学校长和美国十大老牌名校的大学学术委员会主席为首提出的。也许我1991年已完成近百篇哈密顿图论文许多被大师审到如此令人吃惊的是九十年代初竟已得到哈密顿图大师宋增民理事长电话中对我说“邻域并的哈密顿图做得最好的是海南”使我感到压力。因宋教授和他的硕博士八、九十年代已在国内外发表几十篇邻域并的哈密顿图论文，而我当时仅做一些，如此至今我仍不明白宋教授怎说做得最好的是海南？

宋,增民教授的权威性，如大学三年级学生姜益波转让费达1600万的项目，他为咨询数学家特别只专拜访宋,增民教授求教

宋,增民教授的此邻域并的“哈密尔顿图”项目是该系最先获得国家教育部科技进步奖之一的项目照

Note on the Song-Zhang Theorem for Hamiltonian Graphs

Abstract: An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. Essential independent set is a good idea and it has been resreched in many papers. In 1994 Song and Zhang considered independent set S and proved that if for each independent set S of cardinality k+1, one of the following condition holds: (i) there exist u≠v in S such that d(u)+d(v) ³n or |N(u)ÇN(v)| ³α; (ii) for any distinct pair u and v in S, |N(u)ÈN(v)|³n−max{d(x)|xÎS}, then G is Hamiltonian. In this paper, we further consider essential independent set and proved that if for each essential independent set S of cardinality k+1, one of the following condition holds: (i) there exist u≠v in S such that d(u)+d(v) ³n or |N(u)ÇN(v)| ³α; (ii) for any distinct pair u and v in S, |N(u)ÈN(v)|³n−max{d(x)|xÎS}, then G is Hamiltonian. Many known results on Hamiltonian graphs are corollaries of this result

Keywords. Hamiltonian graphs; Independent set; Essential independent set.

MSC(2000): 05C38; 05C45.

1 Introduction

We consider finite and simple graphs in this paper; undefined nonations and terminology can be found in [1]. In particular, we use V(G),E(G), k(G), a(G) and d(G) to denote the vertex set, edge set, connectivity, independence number and minimum degree of G, repectively. If G is a graph and u,vÎV(G), then a path in G from u to v is called a (u,v)-path of G. If vÎV(G) and H is a subgraph of G, then N_H(v) denotes the set of vertices in H that are adjacent to v in G. Thus, d_H(v), the degree of v relative to H, is |N_H(v)|. We also write d(v)=d_G(v) and N(v)=N_G(v) .If C and H are subgraphs of G, then N_C(H)=È_u_Î_V_(H)N_C(u), and G-C denotes the subgraph of G induced by V(G)-V(C). For vertices u,vÎV(G), the distance between u and v, denoted d(u,v), is the length of a shortest (u,v)-path in G, or ¥ if no such path exists.

Let C_m=x₁x₂…x_mx₁ denote a cycle of oeder m. Define

N⁺c_m(u)={x_i₊₁:x_iÎNc_m(u)},N^-c_m(u)={x_i_-₁:x_iÎNc_m(u)} and define N^±c_m(u)= N⁺c_m(u)ÈN^-c_m(u), where subscripts are taken modulo m. Let SÍV(G), define △(S)=max{d(x): xÎS}.

A subset SÍV(G) is said to be an essential independent set if S is an independent set in G and there exist two distinct vertices x,yÎS with d(x,y)=2. In this paper, essential independent set short for EIS

The four fundamental results are as follows.

Theorem 1.1 (Dirac, [4]).If d(G)³n/2 , then G is Hamiltonian.

Theorem 1.2 (Ore, [12]). If d(u)+d(v)³n for each pair of nonadjacent vertices u,vÎV(G) , then G is Hamiltonian.

Theorem 1.3 (Erdös, Chvátal [3]) If graph G is graph with connectivity κ such that independence number α≤κ, then G is Hamiltonian.

Theorem 1.2 was generalized by Fan [5] who showed that only the pair of vertices with distance 2 are essential in Theorem 1.2

In 1996 Chen et al. considered fuether essential independent set with k vertices and proved the following theorem

Theorem 1.4 (Chen et al., [2]).Let G be a k-connected (k≥2) graph on n≥3 vertices. If max{d(u): uÎS}≥n/2 for any essential independent set S with k vertices in G, then G is Hamiltonian.

In 1997 Liu and Wei considered essential independent set with k+1 vertices and proved

Theorem 1.7 (Liu and Wei., [11]).Let G be a k-connected (k≥2) graph on n≥3 vertices. If max{d(u): uÎS}≥n/2 for any essential independent set S with k+1 vertices in G, then G is Hamiltonian or some nonhamiltonian.

In 2002 Hirohata [10] considered essential independent set with k vertices and obtained the length of longest cycle which correlative to max{d(u): uÎS}. Recently, in [9] Theorem 1.4 and some other results were also generalized in 3-connected graphs

Neighborhood unions has already been proved to be very useful in Hamiltonian graphs. The first use of the generalized degree conditions was to provide another generalization of Dirac’s theorem by faudree et al in 1989.

Theorem 1.8 (Faudree et al, [6]).If G is 2-connected graph and if |N(u)ÈN(v)|≥(2n-1)/3 for each pair of nonadjacent vertices u,vÎV(G), then G is Hamiltonian.

In 1991 Faudree et al considered regarding minimum degree d(G) and obtained

Theorem 1.9 (Faudree et al, [7]).If G is 2-connected graph and if |N(u)ÈN(v)|≥n-d(G) for each pair of nonadjacent vertices u,vÎV(G), then G is Hamiltonian.

In 1994 Song and Zhang [13] considered independent set with k+1 vertices and proved the following theorem (see also theorem 44 of Gould’s survey [8])

Theorem 1.10 (Song and Zhang, [13]).if for each independent set S of cardinality k+1, one of the following condition holds: (i) there exist u≠v in S such that d(u)+d(v) ≥ n or |N(u) ÇN(v)| ≥α; (ii) for any distinct pair u and v in S, |N(u)ÈN(v)|≥ n−max{d(x)|xÎS}, then G is Hamiltonian.

We see that essential independent set had already been researched in the above many papers, so EIS is a very good idea. Therefore, the purpose of this paper is to unify and extend the theorems above by the use of essential independent set and we shall prove the following result.

Theorem .if for each essential independent set S of cardinality k+1, one of the following condition holds: (i) there exist u≠v in S such that d(u)+d(v) ≥ n or |N(u)ÇN(v)| ≥α; (ii) for any distinct pair u and v in S, |N(u)ÈN(v)|≥ n−max{d(x)|xÎS}, then G is Hamiltonian.

Obviously, Our Theorem generalizes Theorem1.1, Theorem1.2, Theorem1.4, Theorem1.8, Theorem1.9 and Theorem1.10.

2 Proof of Theorem

For a cycle C_m=x₁x₂…x_mx₁, we write [x_i,x_j] to denote the section x_ix_i₊₁…x_j of the cycle C_m, where subscripts are taken modulo m. For nonational convenience, [x_i,x_j] will denote the (x_i,x_j)-path x_ix_i₊₁…x_j of C_m, as well as the vertex set of the path. We need to establish the claims.

Claim: If G is 2-connected, and assume that G is not Hamiltonian. Let C_m=x₁x₂…x_mx₁ be a longest cycle of G, H a component of G-C_m, let xÎV(H) and x_iÎN_Cm(x), and let x_jÎN_Cm(H) satisfying {x_i₊₁,x_i₊₂,…x_j_-1}ÇN_Cm(H)=Æ, then the following inequalities (1) to (5) all hold.

Proof. Let P denote a path of H which two end-vertices adjacent to x_i,x_j, respectively. (I): When x_hÎ{x_i₊₁,x_i₊₂,…x_j}\{x_j,x_j_-1} is adjacent to x_j₊₁, then x_h₊₁ is not adjacent to x_i₊₁ and x (otherwise, if x_h₊₁ is adjacent to x_i₊₁, then we obtain cycle C*=x_iPx_jx_j_-1…x_h₊₁x_i₊₁x_i₊₂…x_hx_j₊₁x_j₊₂…x_i which is longer than C_m, a contradiction. Since {x_i₊₁,x_i₊₂,…x_j_-1}ÇN_Cm(H)=Æ, so x_h₊₁ is not adjacent to x). (II): When x_hÎ{x_j₊₁,x_j₊₂,…x_i} is adjacent to x_j₊₁, then x_h_-1 is not adjacent to x_i₊₁ and x( otherwise, if x_h_-1 is adjacent to x_i₊₁, then cycle C*=x_iPx_jx_j_-1…x_i₊₁x_h_-1x_h_-2…x_j₊₁x_hx_h₊₁…x_i is longer than C_m, a contradiction. If x_h_-1 is adjacent to x. Let P’ be a path of H which two end-vertices adjacent to x_h_-1,x_j, respectively. Then C*=x_h_-1P’x_jx_j_-1…x_hx_j₊₁x_j₊₂…x_h_-1 is longer than C_m, a contradiction). (III):When yÎV(G-C_m) is adjacent to x_j₊₁, then y is not adjacent to x_i₊₁ and x ( clearly, y is not in H, so y is not adjacent to x. If y is adjacent x_i₊₁, then cycle C*=x_iPx_jx_j_-1…x_i₊₁yx_j+1x_j₊₂…x_i is longer than C_m, a contradiction). In the above (I) we only do not consider that whether the two vertices {x_j,x_j_-1} adjacent to x_j₊₁or nor. Hence we have

|N(x_i₊₁)ÈN(x)|≤n-(d(x_j₊₁) -|{x_j_-1,x_j}|)-|{x_i₊₁,x}|≤n-d(x_j₊₁). ………(1)

Clearly, all of N⁺_Cm(H)ÈV(H) are not adjacent to x_i₊₁ and x_j₊₁. Hence we also have |N(x_i₊₁)ÈN(x_j₊₁)|≤n-|N⁺_Cm(H) ÈV(H)|≤n-|N⁺_Cm(x)|-|V(H)|. ………(2)

Moreover, if x_j_-1 is adjacent to x_j₊₁, then x_j is not adjacent to x_i₊₁. combine with the discussions above (I), (II) and (III). Thus, there is at least (d(x_j₊₁)-|{x_j}|)-|{x_i₊₁}|-|V(H)| vertices is not adjacent to x_i₊₁. Hence

d(x_i₊₁)≤n-(d(x_j₊₁)-|{x_j}|)-|{x_i₊₁}|-|V(H)|, implies d(x_i₊₁)+d(x_j₊₁)≤n-|V(H)|, ………(3)

Similarly, all of N⁺_Cm(x_j₊₁) ÈN_G_-Cm(x_j₊₁) È{x} is not adjacent to x, thus we have

d(x)≤n-| N⁺_Cm(x_j₊₁) ÈN_G_-Cm(x_j₊₁) È{x}|, implies d(x)+d(x_j₊₁)≤n-1 ………(4)

Clearly, the common neighbor of x_i₊₁) and x are all in C_m. Hence we also have

|N(x_i₊₁)ÇN(x)|≤a-1. ………(5)

Proof of Theorem. Assume that G is not Hamiltonian. Let C_m=x₁x₂…x_mx₁ be a longest cycle of G, H a component of G-C_m. Since G is k-connected, so let xÎV(H),x_iÎN_Cm(x), then |N_Cm(H)|≥k. Let S* denote k vertices of N⁺_Cm(H) with containing vertex x_i₊₁ and let S=S*È{x}. Clearly, S is an EIS. Then G satisfies condition (i) or (ii) of Theorem.

(i) If there exist u≠v in S such that d(u)+d(v) ≥ n or |N(u) ÇN(v)| ≥a.

Since S is an EIS, so a≥k+1. Then by inequalities (3) and (4) of Claim, thus, d(u)+d(v)≥n is impossible. Together with (i), this implies |N(u)ÇN(v)|≥a. By inequality (5) of Claim, if |N(u)ÇN(v)| ≥a, then u,vÎN⁺_Cm(H). Without loss of generality, assume{u,v}={x_i₊₁,x_j₊₁}.

Since C_m is a longest cycle of G, so the common neighbor of N(x_i₊₁)ÇN(x_j₊₁) is not in G-C_m(otherwise, if there exist a component G₁of G-C_m such that uÎV(G₁) and uÎN(x_i₊₁)ÇN(x_j₊₁). Let P be a path of G₁ which two end-vertices adjacent to x_i_,x_j, respectively. Then cycle C*=x_iPx_jx_j_-1…x_i₊₁ux_j₊₁x_j₊₂…x_i is longer than C_m, a contradiction. p.s. V(C*)ÉV(C_m) ). Thus, N(x_i₊₁)ÇN(x_j₊₁)ÍV(C_m), this implies |N(x_i₊₁)ÇN(x_j₊₁)|=|N_Cm(x_i₊₁)ÇN_Cm(x_j₊₁)|=|N^-_Cm(x_i₊₁)ÇN^-_Cm(x_j₊₁)|. Since C_m is a longest cycle of G, so N^-_Cm(x_i₊₁)ÇN^-_Cm(x_j₊₁) is a independent set. (otherwise, if x_k_-1,x_h_-1ÎN^-_Cm(x_i₊₁)ÇN^-_Cm(x_j₊₁) satisfying x_k_-1x_h_-1ÎE(G). (a):When x_k_-1Î{x_i_+2,x_i_+3,…,x_j_-1} and x_h_-1Î{x_j_+2,x_i_+3,…,x_i_-1}. Let P be a path of H which two end-vertices adjacent to x_i and x_j, respectively. Then cycle C*=x_iPx_jx_j_-1…x_kx_j₊₁x_j₊₂…x_h_-1x_k_-1x_k_-2…x_i₊₁x_hx_h₊₁…x_i is longer than C_m, a contradiction. (b): When x_k_-1,x_h_-1Î{x_j_+2,x_i_+3,…,x_i}. Without loss of generality, say h≥k+1. Then cycle C*=x_iPx_jx_j_-1…x_i₊₁x_kx_k₊₁…x_h_-1x_k_-1x_k_-2…x_j₊₁x_hx_h₊₁…x_i is longer than C_m, a contradiction.). Let x be a vertex of H, then {x}È(N^-_Cm(x_i₊₁)ÇN^-_Cm(x_j₊₁)) is also a independent set.。By condition(i) of Theorem that |N^-_Cm(x_i₊₁)ÇN^-_Cm(x_j₊₁)|≥a, this implies |{x}È( N^-_Cm(x_i₊₁)ÇN^-_Cm(x_j₊₁))|≥a+1. It is said that the independence number of G is more than a, but the independence number of G is a, a contradiction.

(ii) If for any distinct pair u and v in S, |N(u)ÈN(v)| ≥ n−max{d(x)|xÎS}.

When △(S)=d(x). Then by inequality (2) of Claim, we have |N(x_i₊₁)ÈN(x_j₊₁)|≤n-d(x)-1, but the condition of (ii) showed that |N(u)ÈN(v)|≥n-△(S), a contradiction.

When △(S)=max{ d(u): uÎN⁺_Cm(H)}. We consider the following cases.

Case 1: | N_Cm(H)|≥3.

In this case, let x_i₁,x_i₂,…,…x_i₍_k_-1),x_i_kÎN_Cm(H) with satisfying {x_i₁₊₁,x_i₁₊₂,…x_i_2-1,x_i₂₊₁,…

x_i₍_k_-1)-1,x_i₍_k_-1)+1,…x_i_k_-1}ÇN_Cm(H)=Æ. Let x ÎV(H) be adjacent to some vertex of { x_i₁,x_i₂,…,…x_i₍_k_-1),x_i_k} and let S={x,x_i₁₊₁,x_i₂₊₁,…x_i₍_k_-1)+1,x_i_k₊₁}. Clearly, S is an EIS. Without loss of generality ,say △(S)=d(x_i_k₊₁).

When x_i_k_-1x_i_k₊₁ÏE(G), then by inequality (1) of the Claim, there exist (d(x_i_k₊₁)-|{x_i_k}|) +|{x_i₍_k_-1)+1,x}| vextices are not adjacent to x_i₍_k_-1)+1 and x ,Hence we have

|N(x_i₍_k_-1)+1)ÈN(x)|≤n-(d(x_i_k₊₁)-|{x_i_k}|)-|{x_i₍_k_-1)+1,x}≤n-d(x_i_k₊₁) -1, a contradiction.

When x_i_k_-1x_i_k₊₁ÎE(G). Without loss of generality, say that x_i_k_+t is not adjacent to x_i_k_-1, and all of {x_i_k_+1,x_i_k₊₂…x_i_k_+t-2,x_i_k_+t-1} are adjacent to x_i_k_-1( clearly, x_i_k_+t must exist in set {x_i_k₊₁,x_i_k₊₂,…x_i₍_k_+1)-1}. Since x_i₍_k_+1)-1 is not adjacent to x_i_k_-1). Then, without loss of generality, say that xÎV(H) is adjacent to some vertex of {x_i₁₊₁,x_i₂₊₁,…x_i₍_k_-1)+1}, let S*={x,x_i₁₊₁,x_i₂₊₁,…x_i₍_k_-1)+1,x_i_k_+t}. Clearly, S* is an EIS ( otherwise, if S* is not independent set, then there exist a longer cycle. Example,if x_i₍_k_{-r )+1} is adjacent to x_i_k_+t, where 1≤r ≤k-1, let P be a path of H which two end-vertices adjacent to x_i₍_k_-r)and x_i_k, then cycle C*= x_i₍_k_{-r )}Px_i_kx_i_k₊₁…x_i_k_+t-1x_i_k_-1x_i_k_-2 …x_i₍_k_{-r )+1}x_i_k_+tx_i_k_+t+1…x_i₍_k_{-r )}is longer than C_m).

In the case, for the above EIS S*={x,x_i₁₊₁,x_i₂₊₁,…x_i₍_k_-1)+1,x_i_k_+t}, we will prove that there does not exist condition (i) of theorem.

First, when w,yÎ{x,x_i₁₊₁,x_i₂₊₁,…x_i₍_k_-1)+1,x_i_k_+t}\{x_i_k_+t}. we can easy to check d(w)+d(y)≤n-1 and |N(w)ÇN(y)|≤α-1.

Next, when w=x_i_k_+t, y=x. Clearly we also have d(w)+d(y)≤n-1 and |N(w)ÇN(y)|≤α-1.

Third, when w=x_i_k_+t, yÎ{x_i₁₊₁,x_i₂₊₁,…x_i₍_k_-1)+1}.

Since x_i_k_-1x_i_k₊₁ÎE(G) and each vertex of {x_i_k_+1,x_i_k₊₂…x_i_k_+t-2,x_i_k_+t-1} is adjacent to x_i_k_-1, so we have that each vertex of {x,x_i₁₊₁,x_i₂₊₁,…x_i₍_k_-1)+1,x_i_k_+t}\{x_i_k_+t} is not adjacent to any vertex of {x_i_k_,x_i_k₊₁…x_i_k_+t-2,x_i_k_+t-1}(otherwise, we easy to get a longer cycle).

Then clearly, for any x_i₍_k_{-r )+1}(1≤r ≤k-1),

(1) if x_hÎ{x_i₍_k_{-r )+1}, x_i₍_k_{-r )+2},…x_i_k_-1} is adjacent to x_i₍_k_{-r )+1}, then x_h_-1 is not adjacent to x_i_k_+t(otherwise, cycle C*= x_i_kx_i_k₊₁x_i_k₊₂…x_i_k_+t-1x_i_k_-1x_i_k_-2…x_hx_i₍_k_{-r )+1} x_i₍_k_{-r )+2)}…x_h_-1x_i_k_+tx_i_k_+t+1…x_i₍_k_{-r )}

Px_i_kis longer than C_m, a contradiction); Similarly, we have

(2) If x_hÎ{x_i_k_+t+1, x_i_k_+t+2,…x_i₍_k_{-r )}}\{x_i₍_k_{-r )}} is adjacent to x_i₍_k_{-r )+1}, then x_h₊₁ is not adjacent to x_i_k_+t.

By above (1) and (2), we have that if there exist p vertices of C_m\{x_i₍_k_{-r )}} is adjacent to x_i₍_k_{-r )+1} (or x_i_k_+t), then there must also exist p vertices of C_m\{ x_i₍_k_{-r )}} is not adjacent to x_i_k_+t (or x_i₍_k_{-r )+1}). And every vertices of H is not adjacent to both x_i₍_k_{-r )+1} and x_i_k_+t, and every vertices of G-C_m-H is at most adjacent to one of {x_i₍_k_{-r )+1}, x_i_k_+t}, and x_i₍_k_{-r )+1} and x_i_k_+t} are not adjacent to both x_i₍_k_{-r )+1} and x_i_k_+t. Hence we have

d(x_i₍_k_{-r )+1})+d (x_i_k_+t)≤n-1.

Then, we have |N^-(x_i₍_k_{-r )+1})ÇN^-(x_i_k_+t)|≤α-1 ( otherwise, by a similer proof of the above Suppose (i), we must get a longer cycle). Namely, |N(x_i₍_k_{-r )+1})ÇN(x_i_k_+t)|≤α-1.

Therefore, when w=x_i_k_+t, yÎ{x_i₁₊₁,x_i₂₊₁,…x_i₍_k_-1)+1}, we also have d(w)+d(y)≤n-1 and |N(w)ÇN(y)|≤α-1.

Now, we consider the condition (ii) of Theorem.

When d(x_i_k_+t)≤max{d(x_ih₊₁):h=1,2,…(k-1)}. Without loss of generality, assume △(S*)=

d(x_ih₊₁), where hÎ{1,2,…(k-1) }. Clearly x_ih₊₁ is not adjacent to x_i_k₊₂(otherwise, cycle C*=x_ihPx_i_kx_i_k₊₁x_i_k_-1x_i_k_-2 …x_ih₊₁x_i_k₊₂x_i_k₊₃…x_ih is longer than C_m). And both x_i_(h-1)+1 and x are all not adjacent to x_i_k₊₁ (otherwise, we must get a longer cycle). Thus, by inequality (1) of Claim, we have

|N(x_i_(h-1)+1)ÈN(x)|≤n-(d(x_ih₊₁)-|{x_ih_-1,x_ih}|)-|{x_i_(h-1)+1,x}|-|{x_i_k₊₁}|≤n-d(x_ih₊₁)-1, a contradiction.

When d(x_i_k_+t)>max{d(x_ih₊₁):h=1,2,…(k-1)}.

In this case, clearly, none of {x_i₍_k_-1)+1,x_i₍_k_-1)+2,…x_i_k_-1} is adjacent to x. By the choice of x_i_k_+t, we have that none of {x_i_k₊₁,x_i_k₊₂,…x_i_k_+t} is adjacent to x_i₍_k_-1)+1 and x (otherwise, if there exist some vertex of {x_i_k₊₁,x_i_k₊₂,…x_i_k_+t} is adjacent to x_i₍_k_-1)+1, then we obtain a cycle longer than C_m). Since C_m is a longest cycle of G.,

(I): When x_i₍_k_-1)+rÎ{x_i₍_k_-1)+2,x_i₍_k_-1)+3,…x_i_k_-2} is adjacent to x_i_k_+t. Then x_i₍_k_-1)+r+1 is not adjacent to x_i₍_k_-1)+1 and x.

(II): When x_i_k_+rÎ{x_i_k_+t,x_i_k_+t+1,…x_i₍_k_-1)} is adjacent to x_i_k_+t, then x_i_k_+r-1 is not adjacent to x_i₍_k_-1)+1 and x.

(III): When x_i_k_+rÎ{x_i_k,x_i_k₊₁,…x_i_k_+t-1}\{x_i_k} is adjacent to x_i_k_+t, then x_i_k_+r is not adjacent to x_i(_k_-1)+1 and x. Similar the discussion of inequality (1) of Claim, we have |N(x_i₍_k_-1)+1)ÈN(x)|≤n-(d(x_i_k_+t)-|{x_i_k}|) -|{x_i₍_k_-1)+1,x}|≤n-d(x_i_k_+t)-1, a contradiction.

Case 2. |N_Cm(H)|=|{x_i,x_j}|=2.

In this case, without loss of generality, assume d(x_i₊₁)≤d(x_j₊₁).

Claim(a): Let x,y be two vertices of H which adjacent to x_i,x_j, respectively. If d(x_i₊₁,x_j₊₁)=2, then H has a hamilton-path of subgraph H with two end-vertices x,y.

Proof of Claim(a). Let P be a longest path of H with two end-vertices x,y. If P is not hamilton-path of subgraph H, let w be a vertex of H-P which adjacent to some vertex of P. Clearly, {x_i₊₁,x_j₊₁,w} is an EIS. And we know that there does not exist condition (i) of Theorem. Thus, there must exist condition (ii) of Theorem, then we can check that w must be adjacent to every vertex of H-{w}( otherwise, by inequality (1) of Claim, we can check that |N(x_i₊₁)ÈN(x)|≤n-(d(x_j₊₁)-|{x_j_-1,x_j})-|{x_i₊₁}|-(|{x}|+1)≤n-d(x_j₊₁)-1, a contradiction.), so we can get a longer path of H with end-vertices x,y than P, a contradiction.

Claim(b): When vertex u of H is adjacent to x_i, then u must be adjacent to x_j.

Proof. If vertex u is not adjacent to x_j. Then, if x_j_-1 is adjacent to x_j₊₁, since C_m is a longest cycle, so x_j is not adjacent to both x_i₊₁ and x, by a similar proof of inequality (1) of Claim, we can check that |N(x_i₊₁)ÈN(x)|≤n-(d(x_j₊₁)-|{x_j}|) -|{x_i₊₁,x}|≤n-d(x_j₊₁)-1, a contradiction.

Subcase 2.1. |V(H)|≥2.

Let {x_i,x_j}=N_Cm(H), x,yÎV(H) are adjacent to x_i,x_j, respectively. And let |V(H)|=h.

Subcase2.1.1. d(x_i₊₁,x_j₊₁) ³3

Subcase2.1.1.1 d(x)³max{d(x_i₊₁),d(x_j₊₁)} or d(y)³max{d(x_i₊₁),d(x_j₊₁)}.

Without loss of generality, say d(x)³max{d(x_i₊₁),d(x_j₊₁)}. Clearly {x, x_i₊₁,x_j₊₁} is an EIS, And we know that there does not exist condition (i) of Theorem. Thus, there must exist condition (ii) of Theorem. But we can check that |N(x_i₊₁)ÈN(x_j₊₁)|≤n-|N(x)|-|{x}|≤ n−max{d(x)|xÎS}-1, contrary to condition (ii) of Theorem.

Subcase 2.1.1.2 Not exist Subcase2.1.1.1

Without loss of generality, say d(x_j₊₁)=max{d(x_i₊₁),d(x_j₊₁),d(x),d(y)}. Since d(x_i₊₁,x_j₊₁) ³3, let x_kÎ{x_j₊₁,x_j₊₂,…x_i} adjacent to x_j₊₁with k is as large as possible. then x_k is not adjacent to x_i₊₁; Let x_hÎ{x_i₊₁,x_i₊₂,…x_j_-1} adjacent to x_j₊₁ with h ia as small as possible. then x_h is not adjacent to x_i₊₁. Hence, we can check |N(x_i₊₁)ÈN(x)|≤n-(d(x_j₊₁)-|{x_j,x_j_-1}|) -|{x_i₊₁,x}|-|{x_k,x_h}|≤n-d(x_j₊₁)-2, a contradiction.

Subcase 2.1.2. d(x_i₊₁,x_j₊₁) =2.

By Claim(a) that H has a Hamilton-path of H with two end-vertices x,y.

(I): If x_kÎ{x_j₊₁,x_j₊₂,…x_i} is adjacent to x_i₊₁, and x_k_+rÎ{x_j₊₁,x_j₊₂,…x_i} is adjacent to x_j₊₁(where r ≥1, and x_k₊₁ is not adjacent to x_i₊₁). Then, none of {x_k₊₁,x_k₊₂,…x_k_+h} is adjacent to x_j₊₁(otherwise, together with Claim(a) that H has a Hamilton-path of H with two end-vertices x,y, we can get a cycle longer than C_m). Hence we have

|N(x_i₊₁)ÈN(x)|≤n-(d(x_j₊₁)-|{x_j_-1,x_j}|) -|{x_i₊₁,x}|-(|{x_k₊₁,x_k₊₂,…x_k_+h}|-1)≤n-d(x_j₊₁)-1,

a contradiction. Similarly, if x_hÎ{x_i₊₁,x_i₊₂,…x_j_-1} is adjacent to x_j₊₁, and x_h_+r is adjacent to x_i₊₁, we also can get a contradiction.

(II): If there dose not exist above case (I). Namely, when x_kÎ{x_j₊₁,x_j₊₂,…x_i} is adjacent to x_j₊₁, then none of {x_j₊₁,x_j₊₂,…x_k_-1} is adjacent to x_i₊₁. When x_hÎ{x_i₊₁,x_i₊₂,…x_j_-1} is adjacent to x_j_+1,then none of {x_h₊₁,x_h₊₂,…x_j} is adjacent to x_i₊₁. In this case, under the conditions of Theorem, when x_kÎ{x_j₊₁,x_j₊₂,…x_i} is adjacent to x_j₊₁, and none of {x_k₊₁,x_k₊₂,…x_i} is adjacent to x_j₊₁, then all of {x_j₊₁,x_j₊₂,…x_k} is adjacent to x_j₊₁, every vertex of {x_k,x_k₊₁,…x_i} is all adjacent to x_i₊₁. Similarly, when x_tÎ{x_i₊₁,x_i₊₂,…x_j} is adjacent to x_i₊₁, and none of {x_t₊₁,x_t₊₂,…x_j} is adjacent to x_i₊₁, then every vertex of {x_i₊₁,x_i₊₂,…x_t} is all adjacent to x_i₊₁. every vertex of {x_t,x_t₊₁,…x_j} is adjacent to x_j₊₁ (otherwise, we must have |N(x_i₊₁)ÈN(x)|≤n-d(x_j₊₁)-1, a contradiction). Clearly, x_k_-1 is not adjacent to any of {x_k,x_k₊₁,…x_t}-{x_k,x_t} and x_k_-1 is not adjacent to x_j(otherwise, we obtain a longer cycle). Then, if d(x_i₊₁)≤d(x_k_-1). We have

|N(x_i₊₁)ÈN(x)|≤n-(d(x_k_-1)-|{x_k,x_t}|)-|{x_i₊₁,x,x_j}|≤n-d(x_k_-1)-1, a contradiction.

If d(x_i₊₁)>d(x_k_-1). We have |N(x_k_-1)ÈN(x)|≤n-(d(x_i₊₁)-|{x_k,x_t}|)-|{x_i_-1,x,x_j}|≤n-d(x_i₊₁)-1, a contradiction.

Subcase 2.2.|V(H)|=1.

Let V(H)={x}, | N_Cm(x)|=|{x₁,x_h}| . In this case, we have C_m=C_n_-1. Otherwise, if C_m≠C_n_-1, by not subcase 2.1 and subcase 2.2.1, then for any a component H’ of G-C_m-H. |V(H’)|=1. Without loss of generality, let V(H’)={y}, so |N_Cm(y)|=2. this implies |N(x)ÈN(y)|≤4. Since C_m is a longest cycle, so y is at least not adjacent to one of {x₂,x_h₊₁}, Without loss of generality, say y is not adjacent to x₂, then d(x₂)≤n-|{x,y,x₂,x_h₊₁}|=n-4. clearly S={x,y,x₂} be an EIS, by condition (ii) of Theorem that :for any distinct pair u and v in S, i |N(u)ÈN(v)|≥n-△(S). Toegther with d(x₂)≤n-4, we have |N(x)ÈN(y)|=4 implies m≥4) and d(x₂)=n-4. Since C_m is longest cycle, so we easy to check that m≥6 and n≥8. By inequality (3) of Claim, we have d(x_h₊₁)≤n-|V(H)|-d(x₂)=3. If y is not adjacent to x_h₊₁. so S={x,y,x_h₊₁} is an EIS. Then condition (ii) of Theorem that |N(x)ÈN(y)|≥n-△(S) is fail, a contradiction. If y is adjacent to x_h₊₁. Let N(y)={x_i,x_j}, say i<j. Since C_m is a longest cycle of G. When x_h₊₁=x_i, then x_j_-1 is not adjacent to x₂, we have d(x₂)<n-4, this contradicts the above result that d(x₂)=n-4. When x_h₊₁=x_j. Since C_m is a longest cycle of G, then x_i₊₁ is not adjacent to x₂, and we have d(x₂)<n-4, this contradicts the above result that d(x₂)=n-4.

Therefore, C_m=C_n_-1 holds.

Then, without loss of generality, assume d(x₂)≤d(x_h₊₁). Let S={x,x₂,x_h₊₁}.

Claim (I): x₂ is not adjacent to x_h. Otherwise, we have |N(x₂)ÈN(x)|=d(x₂). By condition (ii) of Theorem that |N(x₂)ÈN(x)|≥n-△(S)=n-d(x_h₊₁), we have d(x₂)i ≥n-d(x_h₊₁) this contradicts the inequality (3) of Claim.

Claim (II): x_h_-1 is adjacent to x_h₊₁. Otherwise, By inequality (3) of Claim and by Claim (I), we further have d(x₂)≤n-(d(x_h₊₁)-|{x_h}|)-|{x₂}|-|{x_h}|-|V(H)|≤n-d(x_h₊₁)-2. But by the condition (ii) of Theorem and Claim (I), we have d(x₂)=|N(x₂)ÈN(x)| -1≥n-△(S) -1=n-d(x_h₊₁) -1, a contradiction.

Claim (III): x₂ is adjacent to x_n_-1. Otherwise, if x₂ is not adjacent to x_n_-1. When d(x₂)=d(x_h₊₁). We can apply the Claim(II) that x₂ is adjacent to x_n_-1, a contradiction. When d(x₂)<d(x_h₊₁). If d(x_n_-1)≥d(x_h_-1), we can apply the Claim(II) that x₂ is adjacent to x_n_-1, a contradiction. If d(x_n_-1) <d(x_h_-1), together with inequality (3) of Claim we have max{d(x₂),d(x_n_-1)}< (n-1)/2. Let S={x,x₂,x_n_-1},clearly, this will contradict the condition (ii) of Theorem.

Claim (IV): Let x_tÎ{x_h₊₁,x_h₊₂,…x_n_-1} is adjacent to x₂ and none of {x_h₊₁,x_h₊₂,…x_t_-2,x_t_-1} is adjacent to x₂; And let x_kÎ{x₂,x₃,…x_h_-1} is adjacent to x_h₊₁ and none of {x₂,x₃,…x_k_-2,x_k_-1} is adjacent to x_h₊₁, then d(x_t_-1)+d(x_k_-1)≤n-3.

Proof of Claim(IV). In this case, then x_t is adjacent to x_h₊₁(otherwise, by inequality (1) of Claim, we have |N(x₂)ÈN(x)|≤n-(d(x_h₊₁)-|{x_h_-1,x_h}|)-|{x₂,x}|-|{x_t_-1}|=n-d(x_h₊₁)-1, this contradicts the condition (ii) of Theorem.

Since C_n_-1 is a longest cycle of G, when x_rÎ{x₂,x₃,…x_h_-1} is adjacent to to x₂, then x_r_-1 is not adjacent to x_t_-1. When x_rÎ{x_t,x_t₊₁,…x_n_-1,x₁}-{x_n_-1,x₁} is adjacent to x₂, then x_r₊₁ is not adjacent to x_t_-1. Clearly, x₂ is not adjacent to x_h and x_h₊₁, and x_t_-1 is not adjacent to x_h_-1 and x_h. Hence we have

d(x_t_-1)≤n-(d(x₂)-|{x_n_-1,x₁}|)-|{x_h_-1,x_h,x_t_-1,x}|=n-d(x₂)-2.

Similarly, we have d(x_k_-1)≤n-d(x_h₊₁) -2.

This implies d(x_t_-1)+d(x_k_-1)≤[n-d(x₂) -2]+[n-d(x_h₊₁) -2]. ……… (6)

By assume d(x₂)£d(x_h₊₁). And by condition (ii) of Theorem, we have d(x₂)+1=|N(x₂)ÈN(x)|≥n-d(x_h₊₁), implies d(x₂)+d(x_h₊₁)≥n-1. By inequality (3) of Claim, we have d(x₂)+d(x_h₊₁)≤n-1, this implies d(x₂)+d(x_h₊₁)=n-1. Together with above inequality (6), we have

d(x_t_-1)+d(x_k_-1)≤[n-d(x₂) -2]+[n-d(x_h₊₁) -2]=n-3. ……… (7)

The following we will prove d(x_k_-1)+d(x_t_-1)≥n-2, which contradicts the above inequality.

First we must get the following claims.

Claim(A). If x_k_-1x_hÎE(G) , then d(x_k_-1)≥d(x_h_-1); If x_k_-1x_hÏE(G), then d(x_k_-1)≥d(x_h_-1) -1.

Proof. If one of Claim(A) is fail, then. By condition (ii) of Theorem, and clearly {x,x_n_-1,x_k_-1} is an EIS, we have

d(x_n_-1)+1=|N(x_n_-1)ÈN(x)|≥n-△{x,x_n_-1,x_k_-1}. ……… (8)

If d(x_k_-1)≥d(x_n_-1).Then inequality (8) can be d(x_n_-1)+1≥|N(x_n_-1)ÈN(x)|≥n-△{x,x_n_-1,x_k_-1}= n-d(x_k_-1), Since Claim(A) is fail, hence the right of the inequality

n-d(x_k_-1)>n-d(x_h_-1). Namely, d(x_n_-1)+1>n-d(x_h_-1)

this implies d(x_n_-1)+d(x_h_-1)>n-1, this contradicts inequality (3) of Claim that d(x_n_-1)+d(x_h_-1)£n-1.

If d(x_k_-1)<d(x_n_-1). Combine with the above hypothesis that d(x_n_-1)≤d(x_h_-1),

And if all of Claim(A) are fail, then

When x_k_-1x_hÎE(G) d(x_h_-1)+1>d(x_k_-1)+1³|N(x_k_-1)ÈN(x)| ……… (9)

When x_k_-1x_hÏE(G) d(x_h_-1)+1>d(x_k_-1)+2³|N(x_k_-1)ÈN(x)| ……… (10)

The right of two inequalities above |N(x_k_-1)ÈN(x)|≥n-△{x,x_n_-1,x_k_-1}=n-d(x_n_-1), all implies d(x_n_-1)+d(x_h_-1)>n-1, this contradicts inequality (3) of Claim that d(x_n_-1)+d(x_h_-1)£n-1.

Thus, all of Claim (A) are true.

Claim (B ). If x_t_-1x_nÎE(G), then d(x_t_-1)≥d(x_n_-1). If x_t_-1x_nÏE(G), then d(x_t_-1)≥d(x_n_-1) -1.

By a proof similar to Claim (A), so the Proof of Claim (B) is omitted.

( The Proof of Claim (B) is following. If one of Claim(B) is fail, then. By condition (ii) of Theorem, and clearly {x,x_h_-1,x_t_-1} is an EIS, we hav

d(x_h_-1)+1=|N(x_h_-1)ÈN(x)|≥n-△{x,x_h_-1,x_t_-1}. ……… (11)

If d(x_t_-1)≥d(x_h_-1).Then inequality (11) can be d(x_h_-1)+1≥|N(x_h_-1)ÈN(x)|≥n-△{x,x_h_-1,x_t_-1}= n-d(x_t_-1), Since Claim(A) is fail, hence the right of the inequality

n-d(x_t_-1)>n-d(x_n_-1). Namely, d(x_n_-1)+1>n-d(x_h_-1)

this implies d(x_n_-1)+d(x_h_-1)>n-1, this contradicts inequality (3) of Claim that d(x_n_-1)+d(x_h_-1)£n-1.

If d(x_t_-1)<d(x_h_-1).,

And if all of Claim(A) are fail, then

When x_t_-1x_nÎE(G) d(x_n_-1)+1>d(x_t_-1)+1³|N(x_t_-1)ÈN(x)|

When x_t_-1x_nÏE(G) d(x_n_-1)+1>d(x_t_-1)+2³|N(x_t_-1)ÈN(x)|

The right of two inequalities above |N(x_t_-1)ÈN(x)|≥n-△{x,x_h_-1,x_t_-1}=n-d(x_h_-1), all implies d(x_n_-1)+d(x_h_-1)>n-1, this contradicts inequality (3) of Claim that d(x_n_-1)+d(x_h_-1)£n-1. )

Then, when x_k_-1 is adjacent to x_h; or x_t_-1 is adjacent to x_n. We have d(x_k_-1)+d(x_t_-1)≥d(x_n_-1)+d(x_h_-1) -1=n-2. This contradicts inequality (7).

When x_k_-1 is not adjacent to x_h; and x_t_-1 is not adjacent to x_n. We have d(x_k_-1)+d(x_t_-1)≥d(x_n_-1)+d(x_h_-1)-2=n-3. Together with inequality (7), we have d(x_k_-1 )+d(x_t_-1)= n-3.

Then clearly, x_k_-1x_t_-1ÏE(G) ( If x_k_-1x_t_-1ÎE(G), then easily we have C_n, a contradiction). And clearly, x_k_-1x₁ÏE(G) and x_t_-1x_hÏE(G) (otherwise, if x_k_-1x₁ÎE(G)or x_t_-1x_hÎE(G), we will get C_n, a contradiction). Since x_k_-1x_hÏE(G) and x_t_-1x_nÏE(G). So all of {x_k_-1,x_t_-1, x₁,x_h} are not adjacent to both x_k_-1and x_t_-1. Together with d(x_k_-1 )+d(x_t_-1)= n-3, then both x_k_-1 and x_t_-1 must have at least a common neighbor vertex. So {x,x_t_-1,x_k_-1} is an EIS.

Without loss of generality, assume d(x_t_-1)≥d(x_k_-1).

By condition (ii) of Theorem, we have d(x_k_-1)+2=|N(x_k_-1)ÈN(x)|≥n-△{x,x_t_-1,x_k_-1}= n-d(x_t_-1), implies d(x_k_-1)+ d(x_t_-1)≥n-2, which contradicts inequality (7)

Therefore, the proof of Theorem is complete.

References

[1] J.A. Bondy, U.S.R. Murty, Graph theory with applications, Macmillan London ,New York,1976.

[2] G.T.Chen, Y.Egawa, X.Liu and A. Saito, Essential independent set and Hamiltonian cycles, J.Graph Theory 21(1996) 243-250

[3] V Chvátal, P Erdös, A note on Hamiltonian circuits, Discrete Math. 2 (1972), 111-113.

[4] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math.Soc.2(1952) 69-81.

[5] G.H. Fan, New sufficient conditions for cycles in graphs, J.Combin.Theory Ser.B 37 (1984), 221-227

[6] R.J.Faudree, R.J.Gould, M.S.Jacobson and R.H.Schelp, Neighborhood unions and Hamiltonian properties in graphs, J. Combin. Theory Ser. B 47 (1989), 1, 1-9.

[7] R.J.Faudree, R.J.Gould, M.S. Jacobson, R.H.Schelp and L.Lesniak, Neighborhood unions and highly Hamilton graphs, Ars Combinatoria 31(1991) 139-148.

[8] R.J.Gould, Advances on the Hamiltonian problem—A survey, Graph and Combin. 19(2003), 7-52.

121-157.

[9] R.J. Gould, K. Zhao, A new sufficient condition for Hamiltonian graphs, Arkiv för Matematik, 44 (2006),2, 299-308

[10] K. Hirohata, Essential independent sets and long cycles, Discrete Math. 250 (2002), 1-3, 109-123.

[11] X. Liu, B. Wei, A generalization of Bondy's and Fan's sufficient conditions for Hamiltonian graphs, Discrete Math. 169 (1997) 249-255

[12] O. Ore., Note on Hamiltonian circuits, Amer.Math.Monthly 67 (1960), 55.

[13] Z. Song, K. Zhang, Neighborhood unions and Hamiltonian properties, Discrete Math.133(1994) 319-324.

摘要：1994年宋,增民教授和张,克民教授在《Discrete Math.》证明： G是独立数为a的k连通n≥3阶图，对图G的任一恰有k+1的点的独立点集S，若满足下列条件之一，则是哈密尔顿图

(i) 存在u,vÎS,使d(u)+d(v)≥n或|N(u)ÇN(v)|≥a;

(ii) 对S中任意两点u,v,均有|N(u)ÈN(v)|≥n-△(S)

因宋老师和张老师的条件没有涉及世界著名的范定理等。如此，本文中，我们进一步研究改进上面条件的任一含距离是２的两点的恰有k+1的点的独立点集S（即我们考虑著名的Essential 独立集）。即下面（I）和（II）相应改进上面宋-张定理，更著名的‘范型’（III）改进范定理等系列世界著名的定理。因此，我们的定理不仅改进上面定理，也改进Dirac定理、Ore定理、范定理、Erdös-Chvátal定理、Faudree-Gould定理等世界著名的几个定理

即我们证明： G是独立数为a的k连通n≥3阶图，对图G的任一含距离是２的两点的恰有k+1的点的独立点集S，若满足下列条件之一，则是哈密尔顿图

(I)存在u,vÎS,使d(u)+d(v)≥n或|N(u)ÇN(v)|≥a;

(II)对S中任意两点u,v,均有|N(u)ÈN(v)|≥n-△(S)

（III）对S中含满足1≤|N(u)ÇN(v)|≤a-1的两点的任意k的点的点集S* ,均有max{d(u),uÎS*}≥n/2.

关键词：哈密尔顿图；邻域并条件；Essential 独立集。

中图分类号：0157.5 MS（2000）分类号：05C38；05C45。

本文研究的图G=(V,E)均是简单图，a(G)、k(G)和d(G)分别表示图G的独立数、连通度和最小度。S是一个点集，则记△(S)=maxd(x): xÎS}。记u是G 的一点，G₁和H为G的两个子图，和记N_G1(u)={vÎV(G₁):uvÎE(G)}。N_G1(H)=È_u_Î_V(H)N_G1(u),N_G(u)可简记为N(u)，N[u]=N(u)È{u}，图G长为m的圈标记为C_m：x₁x₂…x_mx₁, N⁺c_m(u)={x_i+1：x_iÎNc_m(u)},N^-c_m(u)={x_i-1：x_iÎNc_m(u)},N^±c_m(u)= N⁺c_m(u)ÈN^-c_m(u)。

A set S of vertices of graph G is said to be an essential independent set if S is independent set and has two distinct vertices x and y with d(x,y)=2。Essential independent set简写为EIS

正如哈密尔顿图权威Gould RJ在1991年撰写的名为“Updating the Hamiltonian problem---a survey”的世界著名的综述文章[1]引言写下：There are four fundamental results that I feel deserve special attention here—both for their contribution to the overall theory and for their affect on the development of the area. In many ways, these four results are the foundation of much of today’s work.

Gould, RJ上面所指的四个经典结果是：

伦顿大学的著名数学家Dirac于1952年得到的哈密顿图的开创性结果：

定理 1^[2] (Dirac)：如果n阶图G的d(G)³n/2，则G是哈密尔顿图。

耶鲁大学著名图论学家Ore在1960年得到的进一步的结果：

定理 2^[3](Ore.).：如果n阶图G 的不相邻的任意两点u,v均有d(u)+d(v)≥n，则G是哈密尔顿图。

滑铁卢大学的Bondy和时在斯坦福大学的Chvátal在1976年得到的闭包条件。

定理3^[4] (Bondy, Chvátal)：一个n阶图G是哈密尔顿图当且仅当它的闭包C_n(G)是哈密尔顿图.

时在普林斯顿大学的Erdös和时在斯坦福大学的 Chvátal在1972年得到结果：

定理4^[5] (Chvátal, Erdös)：如果图G的a(G)≤k(G)，则G是哈密尔顿图。

除了上面四个哈密顿图的经典结果，至今邻域并条件也已引发出大量论文。其邻域并条件的基本经典结果是1989年Faudree和Gould等得到的如下结果：

定理5^[6]（Faudree等）：如果2连通n≥3阶图G不相邻的任意两点u,v均有|N(u)ÈN(v)|≥(2n-1)/3，则G是哈密尔顿图。

1991年，Faudree和Gould等又再得到如下邻域并条件的结果：

定理6^[7]（Faudree等）：如果2连通n≥3阶图G不相邻的任意两点u,v均有|N(u)ÈN(v)|≥n-d(G)，则G是哈密尔顿图。

范,更华教授也获得著名的下面结果：

定理7^[8] （Fan）“若图中每对距离为2的点中有一点的度数至少是图的点数的一半，则该图存在哈密顿圈”

1994年，宋,增民教授和张,克民教授在文献[9]证明改进上面几个定理的新条件（此论文是Gould, RJ在2003年发表的哈密顿图综述文章[10]引用的248篇论文之一。其中现在国内工作的我国数学家有19篇论文被引用）：

定理7^[9](Song, Zhang)：G是独立数为a的k连通n≥3阶图，对图G的任一恰有k+1的点的独立点集S，若满足下列条件之一，则G是哈密尔顿图：

(i)存在u,vÎS,使d(u)+d(v)≥n或|N(u)ÇN(v)|≥a;

(ii)对S中任意两点u,v,均有|N(u)ÈN(v)|≥n-△(S)。

本文中，我们得到包含和改进上面除了等价条件的闭包方法外的所有条件的如下新条件：

定理: G是独立数为a的k连通n≥3阶图，对图G的任一含距离是２的两点的恰有k+1的点的独立点集S，若满足下列条件之一，则是哈密尔顿图：

(i)存在u,vÎS,使d(u)+d(v)≥n或|N(u)ÇN(v)|≥a;

(ii)对S中任意两点u,v,均有|N(u)ÈN(v)|≥n-△(S)。

（iii）对S中任意含距离是２的两点的k的独立点的点集S* ,均有max{d(u),uÎS*}≥n/2.

下面先证明断言。

断言：若G不是哈密尔顿图，记C_m:x₁x₂…x_mx₁为G的一个最长圈，H为G-C_m的一分支，因G是2连通，所以有xÎV(H),x_iÎN_Cm(x),x_jÎN_Cm(H)且{x_i+1,x_i+2,…x_j-1}ÇN_Cm(H)=Ф，则有下面不等式（1）至不等式（5）成立。

证明：记H中一条两端点和x_i,x_j分别相邻的路为P，其后(I):当x_hÎ{x_i+1,x_i+2,…x_j}\{x_j,x_j-1}和x_j+1相邻时，则x_h+1和x_i+1,x均不相邻(因若x_h+1和x_i+1相邻，则有圈C*:x_iPx_jx_j-1…x_h+1x_i+1x_i+2…x_hx_j+1x_j+2…x_i比C_m长，矛盾；x_h+1和x相邻，记P’是H中一条两端点和x_h+1,x_j分别相邻的路，则有圈C*:x_h+1P’x_jx_j-1…x_hx_j+1x_j+2…x_h+1比C_m长，矛盾)；(II):当x_hÎ{x_j+1,x_j+2,…x_i}和x_j+1相邻时，则x_h-1和x_i+1,x均不相邻(因若x_h-1和x_i+1相邻，则有圈C*:x_iPx_jx_j-1…x_i+1x_h-1x_h-2…x_j+1x_hx_h+1…x_i比C_m长,矛盾; x_h-1和x相邻，记P’是H中一条两端点和x_h-1,x_j分别相邻的路，则有圈C*:x_h-1P’x_jx_j-1…x_hx_j+1x_j+2…x_h-1比C_m长，矛盾);(III):当yÎV(G-C_m)和x_j+1相邻时，y和x_i+1,x不相邻（显然此时y不在H中，所以y和x不相邻；若y和x_i+1相邻，则有圈C*:x_iPx_jx_j-1…x_i+1yx_j+1x_j+2…x_i比C_m长，矛盾）。从（I）知道我们不考虑和x_j+1相邻的两点{x_j,x_j-1}和x_j+1，

建立

u for uÏV(C)

f(u)í u⁺ for uÎu₁C^®u₂^{- -}\{u₁⁺}

u for u=u₂^-

u⁺for uÎu₂⁺C^®v₂\{v₂}

u^-for uÎv₂⁺C^®u^-

从而有|N(x_i+1)ÈN(x)|≤n-(d(x_j+1)-|{x_j-1,x_j}|)-|{x_i+1,x}|≤n-d(x_j+1). ………（1）

显然N⁺_Cm(H) ÈV(H)中点和x_i+1,x_j+1均不相邻，则有|N(x_i+1)ÈN(x_j+1)|≤n-|N⁺_Cm(H) ÈV(H)|≤n- |N⁺_Cm(x)|-| V(H)|. ………（2）

另外，当{x_i+1,x_i+2,…x_i-1}中的x_j-1和x_j+1相邻时，则x_j和x_i+1不相邻。一起结合上面的（I）（II）（III），从而有(d(x_j+1)-|{x_j}|)-|{x_i+1}|-|V(H)|多个点和x_i+1不相邻，即有

d(x_i+1)≤n-(d(x_j+1)-|{x_j}|)-|{x_i+1}|-|V(H)|,有d(x_i+1)+d(x_j+1)≤n-|V(H)|, ………（3）

类似地，显然N⁺_Cm(x_j+1) ÈN_G-Cm(x_j+1) È{x}中点和x均不相邻，从而有

d(x)≤n-| N⁺_Cm(x_j+1) ÈN_G-Cm(x_j+1) È{x}|，有d(x)+d(x_j+1)≤n-1 ………（4）

显然，x_h-1和x的公共邻点只能在圈C_m上，所以有

|N(x_i+1)ÇN(x)|≤a-1. ………（5）

定理的证明：若G不是哈密尔顿图，记C_m:x₁x₂…x_mx₁为G的一个最长圈，H为G-C_m的一分支，xÎV(H),x_iÎN_Cm(x)，因G是k连通的，所以有|N_Cm(H)|≥k，记S’为N⁺_Cm(H)中含x_i+1的k个点，和记S=S’È{x}。显然S是EIS

(i)若存在u,vÎS,使d(u)+d(v)≥n或|N(u)ÇN(v)|≥a。

显然a≥k+1，此时由断言的（3）和（4）知道不可能有d(u)+d(v)≥n 。因此，此时只有|N(u)ÇN(v)|≥a这种可能，再由断言的（5）知，只能存在x_i+1,x_j+1ÎN⁺_Cm(H)使|N(x_i+1)ÇN(x_j+1)|≥a。

此时，因C_m是最长圈，显然, N(x_i+1)ÇN(x_j+1)没有点在G-C_m中（否则，若G-C_m的分支G₁有点uÎN(x_i+1)ÇN(x_j+1),则记P为G₁中一条两端点和x_i,x_j分别相邻的路，则有圈C*:x_iPx_jx_j-1…x_i+1ux_j+1x_j+2…x_i比C_m长，矛盾，且C*含C_m的所有点）,所以N(x_i+1)ÇN(x_j+1)中点全在C_m中，即|N(x_i+1)ÇN(x_j+1)|=|N_Cm(x_i+1)ÇN_Cm(x_j+1)|=|N^-_Cm(x_i+1)ÇN^-_Cm(x_j+1)|，又C_m是最长圈,所以N^-_Cm(x_i+1)ÇN^-_Cm(x_j+1)全部点和H中任取一点组成的点集中没有相邻的两点（比如，若x_k-1、x_h-1ÎN^-_Cm(x_i+1)ÇN^-_Cm(x_j+1), 使x_k-1x_h-1ÎE(G),(a):当x_k-1Î{x_i+2,x_i+3,…,x_j-1}, x_h-1Î{x_j+2,x_i+3,…,x_i-1}时，记P为H中一条两端点分别和x_i和x_j相邻的路，则有圈C*:x_iPx_j

x_j-1…x_kx_j+1x_j+2…x_h-1x_k-1x_k-2…x_i+1x_hx_h+1…x_i比C_m长，矛盾，且C*含C_m的所有点；(b):当x_k-1,x_h-1Î{x_j+2,x_i+3,…,x_i}时,不妨认为h≥k+1,则有圈C*:x_iPx_jx_j-1…x_i+1x_kx_k+1…x_h-1x_k-1x_k-2…x_j+1x_hx_h+1…x_i比C_m长，矛盾，且C*含C_m的所有点）,即这样的互不相邻点一共不少于α+1，和独立数是α矛盾。所以|N(u)ÇN(v)|≤α-1。

(ii)若对任意S中的任意两点u,v均有|N(u)ÈN(v)|≥n-△(S)。

当S中的最大度点是x。

则由断言的（2），有|N(x_i+1)ÈN(x_j+1)|≤n-d(x)-1,和上面定理条件|N(u)ÈN(v)|≥n-△(S)矛盾。

当S中的最大度点在N⁺_Cm(H)中时。

我们分情况讨论如下：

情况1：| N_Cm(H)|≥3。

此时，记x_i1,x_i2,…,…x_i(_k_-1),x_i_kÎN_Cm(H)且要满足{x_i1+1,x_i1+2,…x_i2-1,x_i2+1,…x_i(_k_-1)-1,

x_i(_k_-1)+1,…x_i_k_-1}ÇN_Cm(H)=Ф,记x 为H中和{ x_i1,x_i2,…,…x_i(_k_-1),x_i_k}某点相邻的一点，记S={x,x_i1+1,x_i2+1,…x_i(_k_-1)+1,x_i_k₊₁}，则S是EIS。不妨认为△(S)=d(x_i_k₊₁)。

若x_i_k_-1x_i_k₊₁ÏE(G)，则由断言的（1），将有|N(x_i(_k_-1)+1)ÈN(x)|≤n-(d(x_i_k₊₁)-|{x_i_k}|)-|{x_i(_k_-1)+1,

x_})≤n- d(x_i_k₊₁)-1,矛盾。

若x_i_k_-1x_i_k₊₁ÎE(G)，记x_i_k_+t是和x_i_k_-1不相邻,而x_i_k_+1,x_i_k₊₂…x_i_k_+t-2,x_i_k_+t-1是和x_i_k_-1均相邻的点（显然这样的点存在于{x_i_k₊₁,x_i_k₊₂,…x_i(_k_+1)-1}中，如x_i(_k_+1)-1就和x_i_k_-1不相邻）。其后，取S’={x,x_i1+1,x_i2+1,…x_i(_k_-1)+1,x_i_k_+t}，其中x和k-1个点中之一点相邻，则S’是EIS。（因为显然它是独立集。否则，将有更长圈。比如若x_i(_k_-i)+1和x_i_k_+t相邻，其中1≤i≤k, 其后记P为H中一条两端点和x_i(_k_-i),x_i_k分别相邻的路，则有比C_m更长的圈x_i(_k_-i)Px_i_kx_i_k₊₁…x_i_k_+t-1x_i_k_-1x_i_k_-2 …x_i(_k_+i)+1x_i_k_+tx_i_k_+t+1…x_i(_k_-i)）。

当d(x_i_k_+t)≤max{d(x_it+1):t=1,2,…(k-1)}时。不妨认为△(S’)=d(x_ih+1)，显然x_ih+1和x_i_k₊₂不相邻（否则有比C_m更长的圈x_ihPx_i_kx_i_k₊₁x_i_k_-1x_i_k_-2 …x_ih+1x_i_k₊₂x_i_k₊₃…x_ih），x_i(h-1)+1,x均和x_i_k₊₁不相邻（否则有比C_m更长的圈），所以断言的（1）不等式右边在可减去有，

|N(x_i(h-1)+1)ÈN(x)|≤n-(d(x_ih+1)-|{x_ih-1,x_ih}|)-|{ x_i(h-1)+1,x}|-|{x_i_k₊₁}|≤n- d(x_ih+1)-1,矛盾。

当d(x_i_k_+t)＞max{d(x_it+1):t=1,2,…(k-1)}时。

显然{x_i(_k_-1)+1,x_i(_k_-1)+2,…x_i_k_-1}中点和x均不相邻，根据x_i_k_+t的选择，有{x_i_k₊₁,x_i_k₊₂,…x_i_k_+t}中点和x_i(_k_-1)+1, x均不相邻(否则，如果 {x_i_k₊₁,x_i_k₊₂,…x_i_k_+t} 中有点和 x_i(_k_-1)+1,则有更长圈)。因C_m为G的一个最长圈，所以，（I）：当{x_i(_k_-1)+2,x_i(_k_-1)+3,…x_i_k_-2}中点x_i(_k_-1)+r和x_i_k_+t相邻时，则x_i(_k_-1)+r+1和x_i(_k_-1)+1,x均不相邻；（II）：当{x_i_k_+t,x_i_k_+t+1,…x_i(_k_-1)}中点x_i_k_+r和x_i_k_+t相邻时，则x_i_k_+r-1和x_i(_k_-1)+1,x均不相邻；（III）：当{x_i_k,x_i_k₊₁,…x_i_k_+t-1}\{x_i_k}中点x_i_k_+r和x_i_k_+t相邻时，则x_i_k_+r和x_i(_k_-1)+1,x均不相邻。其后类似断言的（1）的分析，将有|N(x_i(_k_-1)+1)ÈN(x)|≤n-(d(x_i_k_+t)-|{x_i_k}|-|{x_i(_k_-1)+1,x}|≤n- d(x_i_k_+t)-1,矛盾。

情况2：| N_Cm(H)|=|{x_i,x_j}|=2。

此时，认为d(x_i+1)≤d(x_j+1)。我们断言(a):H是完全子图。否则，取x,y为H中距离是2的两点。如果 max {d(x),d(y)}≥d(x_j+1)，由情况1，易有矛盾。如果max {d(x),d(y)}≤d(x_j+1)，有|N(x)ÈN(y)|≤n-(d(x_i+1)-|{x_i,x_j}|)-|{x_i+1,x_j+1}|-|{x,y}|≤n-d(x_j+1)-2，矛盾。

断言(b):H的每一点都和x_i,x_j均相邻。否则，若H中有x和x_j不相邻，类似有|N(x_i+1)ÈN(x)|≤n- (d(x_j+1)-|{x_j}|-|{x_i+1,x}≤n- d(x_j+1)-1，矛盾。两断言正确。

子情况2.1：|V(H)|≥2.

记x_i,x_jÎN_Cm(H), |V(H)|=h,(I):若有x_kÎ{x_j+1,x_j+2,…x_i}和x_i+1相邻，也有x_k+rÎ{x_j+1,

x_j+2,…x_i}和x_j+1相邻(r是自然数，且认为x_k+1和x_i+1不相邻),则显然{x_k+1,x_k+2,…x_k+h}中点和x_j+1均不相邻（否则，因H 是完全子图，将有更长的圈）,

从而有|N(x_i+1)ÈN(x)|≤n-(d(x_j+1)-|{x_j-1,x_j}|-|{x_i+1,x}|-(|{x_k+1,x_k+2,…x_k+h}|-1)≤n-d(x_j+1)-1,矛盾。同样若x_hÎ{x_i+1,x_i+2,…x_j-1}和x_j+1相邻时，也有x_h+r和x_i+1相邻时,也有矛盾。

（II）：没有情况（I）。即当x_kÎ{x_j+1,x_j+2,…x_i}和x_j+1相邻，则{x_j+1,x_j+2,…x_k-1}中点和x_i+1均不相邻；同时当x_hÎ{x_i+1,x_i+2,…x_j-1}和x_j+1相邻时，则{x_h+1,x_h+2,…x_j}中点和x_i+1均不相邻。此时，要满足定理条件，必有当x_k∈{x_j+1,x_j+2,…x_i} 和 x_j+1相邻而{x_k+1,x_k+2,…x_i}的每点和x_j+1均不相邻时，则{x_j+1,x_j+2,…x_k}的每点和x_j+1均相邻，{x_k,x_k+1,…x_i}的每点和x_i+1也均相邻。类似地，当x_t∈{x_i+1,x_i+2,…x_j}和x_i+1相邻而{x_t+1,x_t+2,…x_j}中点和x_i+1均不相邻时，则{x_i+1,x_i+2,…x_t}的每点和x_i+1均相邻，{x_t,x_t+1,…x_j}的每点和x_j+1也均相邻(否则，易有|N(x_i+1)ÈN(x)|≤n-d(x_j+1)-1, 矛盾)。也容易看出x_k-1和x_j不相邻（否则易有更长圈）。其后，如果d(x_i+1)≤d(x_k-1)。则易计算|N(x_i+1)ÈN(x)|≤n-(d(x_k-1)-|{x_k,x_t}|)-|{x_i+1,x,x_j}|≤n-d(x_k-1)-1,矛盾。如果d(x_i+1)＞d(x_k-1)。也易计算|N(x_k-1)ÈN(x)|≤n- (d(x_i+1)-|{x_k,x_t}|)-|{x_i-1,x,x_j}|≤n-d(x_i+1)-1,矛盾。

子情况2.2：|V(H)|=1.

记V(H)={x}，| N_Cm(x)|=|{x₁,x_h}|

我们断言C_m=C_n-1。否则，因为没有子情况2.1和子情况2.2.1，则对G-C_m-H的任一分支H’（此时H’是一点，记为y），均有|N_Cm(y)|=2。则|N(x)ÈN(y)|≤4,显然y和x₂或x_h+1不相邻（认为和x₂不相邻），则易有d(x₂)≤n-|{x,y,x₂,x_h+1}|=n-4，取S={x,y,x₂},要满足定理条件(ii):对S中任意两点u,v,均有|N(u)ÈN(v)|≥n-△(S)，则必有|N(x)ÈN(y)|=4,d(x₂)=n-4。利用这两个等式，其后，要没有更长圈，则易算出此时m≥6,得n≥8。由断言的（3）知，d(x_h+1)≤n-|V(H)|-d(x₂)=3。若y和x_h+1不相邻，取S={x,y,x_h+1},将不满足定理条件|N(x)ÈN(y)|≥n-△(S)，矛盾。若y和x_h+1相邻，记N(y)={x_i,x_j},认为i＜j。要没有更长圈，当x_h+1=x_i时，则必x_j-1和x₂不相邻，得d(x₂)＜n-4，和上面的等式矛盾。当x_h+1=x_j,要没有更长圈，则必x_i+1和x₂不相邻，也有d(x₂)＜n-4，和上面的等式矛盾。得断言C_m=C_n-1成立。

其后，不妨认为d(x₂)≤d(x_h+1)。取S={x,x₂,x_h+1}.

我们断言(1)：x₂和x_h不相邻。否则，|N(x₂)ÈN(x)|=d(x₂)，由定理条件|N(x₂)ÈN(x)|≥n-△(S)=n-d(x_h+1)，得d(x₂)≥n-d(x_h+1)，与断言的（3）矛盾。

我们断言(2)::x_h-1和x_h+1相邻。否则，由断言的（3）进一步有d(x₂)≤n-(d(x_h+1)-|{x_h}|)-|{x₂}|-|{x_h}|-|V(H)|≤n-d(x_h+1)-2，而由定理条件应有d(x₂)=|N(x₂)ÈN(x)|-1≥n-△(S)-1=n-d(x_h+1)-1，矛盾。

我们再断言(3):x₂和x_n-1相邻。否则，当d(x₂)=d(x_h+1)时。类似上面断言(2)有x₂和x_n-1相邻，矛盾；若d(x₂)＜d(x_h+1)时，若d(x_n-1)≥d(x_h-1)，类似断言(2)有x₂和x_n-1相邻，矛盾。若d(x_n-1)＜d(x_h-1)，此时，max{d(x₂),d(x_n-1)}＜(n-1)/2,取S={x,x₂,x_n-1}，显然将不满足定理条件，矛盾。

其后，记x_t是{x_h+1,x_h+2,…x_n-1}中的和x₂均相邻的下标最小的点。此时x_t也和x_h+1相邻（因为若x_t和x_h+1不相邻，由断言（1）将有|(x₂)ÈN(x)|≤n-(d(x_h+1)-|{x_h-1,x_h}|)-|{x₂,x}|-|{x_t-1}|=n-d(x_h+1)-1，和应有定理条件|N(x₂)ÈN(x)|≥n-△(S)=n-d(x_h+1)矛盾）。因C_n-1是最长圈，所以，当x_rÎ{x₂,x₃,…x_h-1}和x₂相邻时，则x_r-1和x_t-1不相邻；当x_rÎ{x_t,x_t+1,…x_n-1}\{x_n-1}和x₂相邻时，则x_r+1和x_t-1不相邻；显然x₂和x_h,x_h+1均不相邻，而x_t-1和x_h-1,x_h均不相邻，从而易有d(x_t-1)≤n-(d(x₂)-|{x_n-1}|)-|{x_h-1,x_h,x_t-1}|=n-d(x₂)-2。类似地记x_k是{x₂,x₃,…x_h-1}中的和x_h+1相邻的下标最小的点，则类似有d(x_k-1)≤n-d(x_h+1)-2。

从而有d(x_t-1)+d(x_k-1)≤[n-d(x₂)-2]+[n-d(x_h+1)-2]=n-3。（*）

认为d(x₂)≥d(x_h+1)。由定理条件有d(x_h+1)+1=|N(x_h+1)ÈN(x)|≥n-d(x₂)，有d(x₂)+d(x_h+1)≥n-1；由断言的（3）有d(x₂)+d(x_h+1)≤n-1，所以推出d(x₂)+d(x_h+1)=n-1。同理：d(x_n-1)+d(x_h-1)=n-1。

认为d(x_n-1)≤d(x_h-1)。

（1）断言：若x_k-1和x_h 相邻，则d(x_k-1)≥d(x_h-1)。否则，若d(x_k-1)<d(x_h-1)。从而定理条件，有d(x_n-1)+1=|N(x_n-1)ÈN(x)|≥n-△{x, x_n-1，x_k-1}

若d(x_k-1)≥d(x_n-1)

则上面不等式d(x_n-1)+1=|N(x_n-1)ÈN(x)|≥n-△{x, x_n-1，x_k-1}= n- x_k-1)> n- d(x_h-1)。与d(x_n-1)+d(x_h-1)=n-1，矛盾。

若d(x_k-1)<d(x_n-1)

则从而定理条件，有d(x_h-1)+1>d(x_k-1)+1=|N(x_k-1)ÈN(x)|≥n-△{x, x_n-1，x_k-1}= n- d(x_n-1)。与d(x_n-1)+d(x_h-1)=n-1，矛盾。所以断言d(x_k-1)≥d(x_h-1)正确。

（2）类似有，若x_k-1和x_h 不相邻，则d(x_k-1)≥d(x_h-1)-1。

（3）同样有若x_t-1和x_n相邻，则d(x_t-1)≥d(x_{n -1})_。否则，若d(x_t-1)<d(x_{n -1})_，则d(x_{n -1})+1> d(x_t-1)+1=|N(x_t-1)ÈN(x)|≥n-△{x, x_t-1，x_h-1}= n- d(x_h-1)_。与d(x_n-1)+d(x_h-1)=n-1，矛盾。

（4）类似有，若x_t-1和x_n 不相邻，则d(x_t-1)≥d(x_{n -1})-1。

若x_k-1和x_h 相邻，或x_t-1和x_n 相邻。则d(x_k-1) +d(x_t-1)≥d(x_{n -1})+d(x_h-1)-1= n-2。与（*）矛盾。所以，只能是：x_k-1和x_h 不相邻，及x_t-1和x_n 不相邻。得

则d(x_k-1) +d(x_t-1)≥d(x_{n -1})+d(x_h-1)-2= n-3。结合（*），得d(x_k-1 )+d(x_t-1)= n-3。

因x_k-1和x_h 不相邻，及x_t-1和x_n 不相邻，所以，x_k-1和 x_t-1的必有公共邻点，显然x_k-1和x_t-1不相邻（否则有比C_n-1长的圈），其后取S={x,x_t-1,x_k-1},认为d(x_t-1)≥d(x_k-1)

则从而定理条件，有 d(x_k-1)+2=|N(x_k-1)ÈN(x)| ≥n-△{x, x_t-1，x_k-1}= n- d(x_t-1)，有

n-3=d(x_k-1)+ d(x_t-1)≥n-2。矛盾。

若（iii）含满足1≤|N(u)ÇN(v)|≤a-1的两点u,v的任意k的点的点集S* ,均有max{d(u),uÎS*}≥n/2.

先证明几个引理：

For a cycle C_m=x₁x₂¼x_mx₁, we write [x_i,x_j] to denote the section x_ix_i+1¼x_j of the cycle C_m,where subscripts are taken modulo m. We need to establish some lemmas.

Lemma 1. Suppose that C_m=x₁x₂¼x_mx₁is a longest cycle of a graph G, H is a component of G-V(C_m,), and x_i,x_j are distinct vertices in N_Cm(H). Then each of the following must hold.

(i) {x_i-1,x_i+1, x_j-1,x_j+1}ÇN_Cm(H)=Ф.

(ii) x_i+1x_j+1ÏE(G) and x_i-1x_j-1ÏE(G).

(iii) If x_tx_j+1ÎE(G) for some vertex x_tÎ [x_j+2,x_i] ,then x_t-1x_i+1ÏE(G) and x_t-1ÏN_Cm(H).

(iv) If x_tx_j+1ÎE(G) for some vertex x_tÎ [x_i+1,x_j-1] , then x_t+1x_i+1ÏE(G).

(v) No vertex of G-(V(C_m)-V(H)) is adjacent to both x_i+1 and x_j+1.

Proof. If any one of (i),(ii) and (v) were to fail, then it is easy to see that G would have a cycle longer than C_m, a contradiction.

Suppose that (iii) fails. Then there exists a vertex x_tÎ{x_j+1,x_j+2,¼x_i} satisfying x_tx_j+1ÎE(G) and either x_t-1x_i+1ÎE(G) or x_t-1 is adjacent to some vertex of H. Suppose first that x_t-1x_i+1ÎE(G), let P¹(H) denote a path of H whose two end-vertices are adjacent to x_i and x_j, respectively. Then x_iP¹(H)x_jx_j-1¼x_i+1x_t-1x_t-2¼x_j+1x_tx_t+1¼x_i is a cycle longer than C_m, a contradiction. Hence if x_tx_j+1ÎE(G) then x_t-1x_i+1ÏE(G). Next we suppose that x_t-1 is adjacent to some vertex of H. Let P²(H)=w₁w₂¼w_rdenote a path of H whose two end-vertices w₁,w_r are adjacent to x_j,x_t-1(or to x_t-1 and x_j ),respectively. Then we have x_jP²(H)x_t-1x_t-2¼x_j+1x_tx_t+1¼x_j is a cycle longer than C_m, a contradiction. Thus if x_tx_j+1ÎE(G), then V(H)ÇN(x_t-1)=Ф.

The proof for (iv) is similar, and so this complete the proof of the lemma.

Lemma 2 . Let G be a 2-connected graph of order n, C_m=x₁x₂¼x_mx₁ be a cycle of G, and H be a component of G-V(C_m). If there exist two distinct vertices x_i+1,x_{j+1 in N}⁺_Cm(H) such that d(x_i+1) ³n/2 and d(x_j+1) ³n/2 or there exists a vertex x_i+1ÎN⁺_Cm(H) and a vertex yÎH such that d(x_i+1) ³n/2 and d(y)³n/2, then there exists a cycle C^* longer than C_m with V(C_m)ÌV(C^*).

Proof. Suppose, to the contrary, that

G does not have a cycle C^* longer than C_m with V(C_m)ÌV(C^*) (1)

Suppose first that there exist two distinct vertices x_i+1, x_{j+1
in N}⁺_Cm(H) such that d(x_i+1) ³n/2 and d(x_j+1) ³n/2. Let xÎV(H), by (1), we must have x_i+1xÏE(G). Since G is 2-connected, we may suppose that H has a path P whose two end-vertices are adjacent to x_i,x_j, respectively. If there exists a x_hÎ{x_i+1,x_i+2,¼x_j}-{x_j}, adjacent to x_j+1, then x_h+1 is not adjacent to x_i+1, For otherwise, x_h+1 is adjacent to x_i+1, and so the cycle C*=x_iPx_jx_j-1¼x_h+1x_i+1x_i+2¼x_hx_j+1x_j+2¼x_i is longer than C_m with C* with V(C_m)ÌV(C^*), contrary to (1). If there exists a x_hÎ{x_j+1,x_j+2,¼x_i}, adjacent to x_j+1, then by a similar argument for the proof of Lemma1 (iii), we conclude that x_h-1 is not adjacent to x_i+1. For otherwise, we have x_h-1x_i+1ÎE(G), and the cycle C*=x_iPx_jx_j-1¼x_i+1x_h-1x_h-2…x_j+1x_hx_h+1x_i is longer than C_m with V(C_m)ÌV(C^*), contrary to (1).

If there exists a yÎV(G-V(H)ÈV(C_m)) adjacent to x_j+1, then y is not adjacent to x_i+1. For otherwise, if yx_i+1ÎE(G), then a cycle C*=x_iPx_jx_j-1¼x_i+1yx_j+1x_j+2x¼x_i longer than C_m with V(C_m)ÌV(C^*), contrary to (1). Again by (1), none of the vertex of H is adjacent to x_i+1or x_j+1.

We define a bijection f on N(x_j+1) as follows: Let vÎN(x_j+1),

v when vÏV(C_m)

f(u)=ív⁺=x_k+1 when v=x_kÎ{x_i+1,x_i+2,…x_j}\{x_j}

v^-=x_k-1when v=x_kÎ{x_j+1,x_j+2,…x_i}

Thus, | f(N(x_j+1))|=d(x_j+1)-|{x_j}|

By the previous arguments, for any yÎf(N(x_j+1)), we have yx_i+1ÏE(G). Since C_m is a longest cycle , so every vertex of H is not adjacent to x_i+1and x_j+1, and f(N(x_j+1))ÇV(H)=φ,

Since x_i+1Ï f(N(x_j+1)) and x_i+1ÏN(x_i+1), Hence we can check that

d(x_i+1)£n-| f(N(x_j+1))|-(|{x_i+1}|+|V(H)|)£n-(d(x_j+1)-|{x_j}|)-(|{x_i+1}|+|V(H)|)£n-|V(H)|.

Since |V(H)| ³1, this implies d(x_i+1)+d(x_j+1) £n-1, a contradiction.

We apply the similar arguments as above to prove that if there exist a vertex x_i+1Î

N⁺_Cm(H) and a vertex yÎV(H) with d(x_i+1) ³n/2 and d(y) ³n/2, then there exists a cycle C^* longer than C_m with V(C_m)ÌV(C^*).

Therefore, Lemma 2 is proved.

Lemma 3. If G is a k-connected (k³2) nonhamiltonian graph of order n, and if max {d(v),vÎS}³n/2 for every independent set S of order k such that S has two distinct vertices x,y with 1£|N(x)ÇN(y)| £a-1. Let C_m=x₁x₂¼x_mx₁ be a longest cycle of G, then for any a component H of G-C_m, there must exist at least a vertex xÎV(H) such that x adjacent to some vertex of C_m d(x) ³n/2.

Proof . Assume ,to the contrary, that Lemma 3 is not true. It is say that there exists a component H of G-C_m, d(x)<n/2 for every xÎV(H) of |N_Cm(x)| ³1.

Since G is k-connected, then |N_Cm(H)| ³k. Clearly the independence number a(G)³k+1. By the assumption of Lemma 3, we can choose a vertex subset V^* of N⁺_Cm(H) with |V*|=k-1 such that there exists a vertex (say x_i+1), x_i+1ÎV* with d(x,x_i+1)=2. Then N(x)ÇN(x_i+1)ÍN_Cm(H). For otherwise, there would be a uÎV(H)ÇN(x)ÇN(x_i+1), which implies a longer cycle C* with V(C^*)=V(C_m)È{x,u}, namely, V(C_m)ÌV(C^*), a contradicion . Since N⁺_Cm(H) is independent set, we have |N_Cm(H)|=|N⁺_Cm(H)|£a(G)-1, which implies 1£|N(x)ÇN(x_i+1)| £a(G)-1. If follows that the vertex set V^*È{x} is a k-element set satisfying the hypothesis of Lemma 3 . Since d(x)<n/2, by thehypothesis of Lemma3, there must be a vertex ( say x_h+1) in V^*satisfying d(x_h+1)³n/2. By the Lemma 2, every vertex of N⁺_Cm(H)\{x_h+1} must have degree less n/2. Since G is k-connected (k³2), there must be some vertex yÎV(H) with x_j+1ÎN⁺_Cm(y)\{x_h+1}(possibly y=x). Similarly, we have 1£|N(y)ÇN(x_j+1)|£a(G)-1. We can choose k-2 vertices of N⁺_Cm(H)\{x_h+1,x_j+1} together with {y,x_j+1} to form a vertex set V**, which also satisfies the hypothesis of Lemma3. Hence there must be a vertex uÎV** such that d(u)³n/2. Since d(x_h+1)³n/2, by Lemma 2, there exists a longer cycle C^* with V(C_m)ÌV(C^*), contrary to the assumption that C_m is a longest cycle.

Lemma 3 is proved.

Proof of Condition (iii) . suppose, to the contrary, that G is not Hamiltonian. Let C_m=x₁x₂¼x_mx₁ be a longest cycle of G, and let H be a component of subgraph G-V(C_m).

We consider the following two cases.

Case1: There exists xÎV(H) satisfying |N_Cm(x)| ³1 and d(x)<n/2.

In this case, since G is k-connected, then |N_Cm(H)| ³k. Clearly the independence number a(G)³k+1. By the assumption of case 1, we can choose a vertex subset V^* of N⁺_Cm(H) with |V*|=k-1 such that there exists a vertex(say x_i+1), x_i+1ÎV* with d(x,x_i+1)=2. Then N(x)ÇN(x_i+1)ÍN_Cm(H) . For otherwise, there would be a uÎV(H)ÇN(x)ÇN(x_i+1), which implies a longer cycle C* with V(C_m)ÌV(C^*), a contradicion . Since N⁺_Cm(H) is independent set, we have |N_Cm(H)|=|N⁺_Cm(H)|£a(G)-1, which implies 1£|N(x)ÇN(x_i+1)| £a(G)-1. If follows that the vertex set V^*È{x} is a k-element set satisfying the hypothesis of Theorem1.6 . Since d(x)<n/2, by the hypothesis of Condition (iii), there must be a vertex ( say x_h+1) in V^*satisfying d(x_h+1)³n/2. By the Lemma 2, every vertex of N⁺_Cm(H)\{x_h+1} must have degree less n/2. Since G is k-connected (k³2), there must be some vertex yÎV(H) with x_j+1ÎN⁺_Cm(y)\{x_h+1}(possibly y=x). Similarly, we have 1£|N(y)ÇN(x_j+1)|£a(G)-1. We can choose k-2 vertices of N⁺_Cm(H)\{x_h+1,x_j+1} together with {y,x_j+1} to form a vertex set V**, which also satisfies the hypothesis of Condition (iii). Hence there must be a vertex uÎV** such that d(u)³n/2. Since d(x_h+1)³n/2, by Lemma 2, there exists a longer cycle C^* with V(C_m)ÌV(C^*), contrary to the assumption that C_m is a longest cycle.

Case2: d(x)³n/2 for every xÎV(H) of |N_Cm(x)|³1.

Without loss of generality, pick x_iÎN_Cm(x), and xÎV(H).

Claim: G-C_m is connected. Suppose not, there exists a component H* in G-V(H)ÈV(C_m). By Lemma 3, there must exist a vertex yÎV(H*) adjacent to some vertex of C_m with d(y)³n/2, which implies d(x)+d(y)³n. On the other hand, if x is adjacent to x_iÎV(C_m), then x is not adjacent to x_i+1and x_i-1. Hence we have d(x)£|V(C_m)|/2+|V(H)\{x}|. Similarly, we have

d(y) £|V(C_m)|/2+|V(H*)\{y}|.

It follows that d(x)+d(y) £ [|V(C_m)|/2+|V(H)\{x}|]+[|V(C_m)|/2+|V(H*)\{y}|]£n-2,

a contradiction. Hence G-C_m is connected. This prove the claim.

Let x_i,x_jÎN_Cm(H) such that {x_i+1,x_i+2,¼x_j-1}ÇN_Cm(H)=Ф with |{x_i+1,x_i+2,¼x_j}| is as small as possible among all pair vertices x_h,x_tÎN_Cm(H) with {x_h+1,x_h+2,¼x_t-1}ÇN_Cm(H)=Ф. By d(x)³n/2, we have |V(H)|³2. For otherwise, |V(H)|=1, and so C_m=C_n-1. By |N_Cm(H)|=d(x) ³n/2, there must exist x_i,x_i+1ÎV(C_n-1) such that x_i,x_i+1 are both adjacent to x, and so G is hamiltonian,a contradiction.

By the choice that |{x_i+1,x_i+2,¼x_j}| is as small as possible, and since |V(H)|+|N_Cm(H)| ³n/2+1,|V(H)|³2, |N_Cm(H)|³2, we have

|{x_i+1,x_i+2,¼x_j-1}|£ (n-|V(H)|-|N_Cm(H)|)/|N_Cm(H)| £ [n-(|V(H)|+|N_Cm(H)|)]/|N_Cm(H)|

£ [n-(1+n/2)]/|N_Cm(H)| £ (n/2-1)/|N_Cm(H)| £ (|V(H)|+|N_Cm(H)|-2)/|N_Cm(H)|

£|V(H)|/|N_Cm(H)|+1-2/|N_Cm(H)|<|V(H)|.

Namely, |{x_i+1,x_i+2,¼x_j-1}|<|V(H)| ¼(2)

Let P(x_i,x_j) be a path of H with the two of its end-vertices adjacent to x_i,x_j of C_m, respectively. Let C¹ be a cycle as long as possible such that C¹ contain every vertex of cycle x_jx_j+1¼x_iP(x_i,x_j)x_j. By the Lemma 2 and Lemma 3 , we can see that there exists a vertex x in every component H_i of G-V(C¹) where x is adjacent to a vertex of C¹ with d(x) ³n/2. For otherwise, there exists an xÎV(H_i) satisfying |N_C¹(x)|³1 and d(x)<n/2. Then we can apply the similar proof of case 1, to obtain a longer cycle C^* with V(C¹)ÌV(C^*), contrary to the choice of C¹. By the silimar arguments as above we can prove that G-C¹=H_i is connected. Clearly, for any vertex x of H_i, we have xÎ{x_i+1,x_i+2,¼x_j-1}ÈV(H),and we can see that every vertex of {x_i+1,x_i+2,¼x_j-1} is not adjacent to any vertex of H, and since H_i is connected, we can have V(H_i)Ç{x_i+1,x_i+2,¼x_j-1}=Ф or V(H_i)ÇV(H)=Ф. If V(H_i) Ç{x_i+1,x_i+2,¼x_j-1}=Ф, we can see that C¹ contains every vertex of C_m and some vertex of H, contrary to the assumption that C_m is a longest cycle. Therefore,we must have V(H_i)ÇV(H)=Ф. Hence for any vertex x of H_i, xÎ{x_i+1,x_i+2,¼x_j-1}. This, together with (2), implies |V(H)|>|{x_i+1,x_i+2,¼x_j}|³|V(H_i)|. Therefore, C¹ contains every vertex of C_m and some vertex of H, contrary to the assumption that C_m is a longest cycle.

Therefore, the proof of Condition (iii) is complete.

先再现原文中一些定义：Let C be a cycle of maximum length in G, let B be any component of G\V(C ), N_C(B)={v₁, v₂, …v_m}. Let x_i be any vertex in B which is adjacent to v_i, u_jÎv_j-1⁺C^®v_j^- such that u_jÏN(v_j⁺), and vÎN(v_j⁺) for all vÎu_j⁺C^®v_j.

其中第5个断言是：

Claim2.5. Let vÎN(u₂)ÈN(x₂).Then vÏu₁C^®v₁ and

(1) if vÎv₁C^®u₂,then u₁v⁺ÏE(G).

(2) if vÎu₁⁺C^®u₁^-,then u₁v^-ÏE(G).

Proof. of Claim2.5. If there exists vÎv₁C^®u₂ such that u₁v⁺ÎE(G), then since u₁v₁⁺ÏE(G), we have vÎv₁⁺C^®u₂^-.Hence by the definition of N_C(B), vÎN(u₂),and the cycle

u₁v⁺C^®u₂vC^¬v₁⁺u₁⁺C^¬v₁x₁Bx₂v₂C^¬u₂⁺v₂⁺C^®u₁

is longer than C,(a contradiction.) If there exists vÎu₂⁺C^®u₁^-, then when vÎN(x₂) such that u₁v^-ÎE(G), the cycle

u₁v^-C^¬v₁⁺u₁⁺C^®v₁x₁Bx₂vC^®u₁

is longer than C;when vÎN(u₂), vÎv₂⁺C^®u₁and the cycle

u₁v^-C^¬v₂⁺u₂⁺C^®v₂x₂Bx₁v₁C^¬u₁⁺v₁⁺C^®u₂vC^®u₂vC^®u₁

is longer than C.

These are contradictions. Claim2.5 holds.

We define a bijection f on N(u₂)ÈN(x₂) as follows: Let uÎN(u₂)ÈN(x₂),

u for uÏV(C)

f(u)í u⁺ for uÎu₁C^®u₂^{- -}

u for u=u₂^-

u^-for uÎv₂⁺C^®u^-

From the previous arguments and Claim2.5,for any uÎf(N(u₂)ÈN(x₂)),we have uu₁ÏE(G). Note that x₂Ïf(N(u₂)ÈN(x₂)) and x₂u₁ÏE(G), and we obtain

t₂≤d(u₁)≤n-|N(u₂)ÈN(x₂)|-1≤t₂-1

a contradiction.Therefore, Theorem 1.4 holds.

首句“Let vÎN(u₂)ÈN(x₂).Then vÏu₁C^®v₁”应是“Let vÎN(u₂)ÈN(x₂).Then vÏu₁C^®v₁\{u₁⁺}”。因为u₂u₁⁺ÎE(G)，这并没有导致有更长圈或其它什么矛盾。而只有vÎu₁C^®v₁\{u₁⁺}（即u₂vÎE(G)）才导致有更长圈的矛盾。

所以补充1：Let vÎN(u₂)ÈN(x₂).Then vÏu₁C^®v₁\{u₁⁺}

其后的：(2) if vÎu₁⁺C^®u₁^-,then u₁v^-ÏE(G).(这里（2）有印刷错误，即u₁⁺C^®u₁^-应是vÎu₂⁺C^®u₁^-，因为u₁⁺C^®u₁^-Év₁C^®u₂，如此，若是u₁⁺C^®u₁^-，则（1）的分析和证明是多余的了。从Claim2.5的下面证明分If there exists vÎv₁C^®u₂和If there exists vÎu₂⁺C^®u₁^-来证明，也看出确实如此)

其后，when vÎN(u₂), vÎv₂⁺C^®u₁and the cycle

u₁v^-C^¬v₂⁺u₂⁺C^®v₂x₂Bx₁v₁C^¬u₁⁺v₁⁺C^®u₂vC^®u₂vC^®u₁

is longer than C知道还没有解决vÎN(u₂), vÎu₂⁺C^®v₂，就是说if there exists vÎÎu₂⁺C^®v such that u₁v^-ÎE(G)，也没有获得圈u₁v^-C^¬v₂⁺u₂⁺C^®v₂x₂Bx₁v₁C^¬

u₁⁺v₁⁺C^®u₂vC^®u₂vC^®u₁，因此，

应补：vÎN(u₂), vÎu₂⁺C^®v₂ such that u₁v⁺ÎE(G) and the cycle

u₁v⁺C^®v₂Bv₁C^¬u₁⁺v₁⁺C^®u₂vC^¬u₂⁺v₂⁺C^®u₁

is longer than C, a contradiction。

接着：

We define a bijection f on N(u₂)ÈN(x₂) as follows: Let uÎN(u₂)ÈN(x₂),

u for uÏV(C)

f(u)í u⁺ for uÎu₁C^®u₂^--

u for u=u₂^-

u^-for uÎu₂⁺C^®u^-

From the previous arguments and Claim2.5,for any uÎf(N(u₂)ÈN(x₂)),we have uu₁ÏE(G). Note that x₂Ïf(N(u₂)ÈN(x₂)) and x₂u₁ÏE(G), and we obtain

t₂≤d(u₁)≤n-|N(u₂)ÈN(x₂)|-1≤t₂-1,

a contradiction. Therefore, Theorem 1.4 holds.

这部分的证明也有两个问题。第一、“f(u)=u^-, for uÎu₂⁺C^®u^-”的定义是行不通的。如uÎu₂⁺C^®v^-, 显然从补充2应是u⁺u₁ÏE(G)而不是u^-u₁ÏE(G)（因为也可能有u^-u₁ÎE(G)，这并没有什么矛盾。而从补充2看到，只有u⁺u₁ÎE(G)才必定有矛盾，所以一定是u⁺u₁ÏE(G)），而且这可能性一定存在，如u=u₂⁺Îu₂⁺C^®v^-，另u₂v₂ÎE(G)和u₂v₂⁺⁺ÎE(G)都有存在的可能且没有矛盾，那和u₂相邻的两点v₂,v₂⁺⁺都只对应一点v₂和u₁不相邻，这时f(u)就不是一一对应，要达到一一对应，就应限制定义域为V(C)\{v₂}或V(C)\{v₂⁺⁺}。

另外，还有补充1，所以必修正为补充3：

u for uÏV(C)

f(u)í u⁺ for uÎu₁C^®u₂^{- -}\{u₁⁺}

u for u=u₂^-

u⁺for uÎu₂⁺C^®v₂\{v₂}

u^-for uÎv₂⁺C^®u^-

其后，“t₂≤d(u₁)≤n-|N(u₂)ÈN(x₂)|-1≤t₂-1”不成立。

Claim2.5. Let vÎN(u₂)ÈN(x₂).Then vÏu₁C^®v₁\{u₁⁺} and

(1) if vÎv₁C^®u₂,then u₁v⁺ÏE(G).

(2) if vÎu₂⁺C^®u₁^-,then u₁v^-ÏE(G).

u₁v⁺C^®u₂vC^¬v₁⁺u₁⁺C^¬v₁x₁Bx₂v₂C^¬u₂⁺v₂⁺C^®u₁

is longer than C,(a contradiction.) If there exists vÎu₂⁺C^®u₁^- such that u₁v^-ÎE(G), then when vÎN(x₂) such that u₁v^-ÎE(G), the cycle

u₁v^-C^¬v₁⁺u₁⁺C^®v₁x₁Bx₂vC^®u₁

is longer than C;when vÎN(u₂), vÎv₂⁺C^®u₁such that u₁v^-ÎE(G) and the cycle

u₁v^-C^¬v₂⁺u₂⁺C^®v₂x₂Bx₁v₁C^¬u₁⁺v₁⁺C^®u₂vC^®u₂vC^®u₁

is longer than C.

When vÎN(u₂), vÎu₂⁺C^®v₂ such that u₁v⁺ÎE(G) and the cycle

u₁v⁺C^®v₂Bv₁C^¬u₁⁺v₁⁺C^®u₂vC^¬u₂⁺v₂⁺C^®u₁

is longer than C, a contradiction

These are contradictions. Claim2.5 holds.

We define a bijection f on N(u₂)ÈN(x₂) as follows: Let uÎN(u₂)ÈN(x₂),

u for uÏV(C)

f(u)í u⁺ for uÎu₁C^®u₂^{- -}\{u₁⁺}

u for u=u₂^-

u⁺for uÎu₂⁺C^®v₂\{v₂}

u^-for uÎv₂⁺C^®u^-

From the previous arguments and Claim2.5,for any uÎf(N(u₂)ÈN(x₂)),we have uu₁ÏE(G). Note that x₂Ïf(N(u₂)ÈN(x₂)) and x₂u₁ÏE(G), 因此，我们推得不等式：

t₂≤d(u₁)≤n-|N(u₂)ÈN(x₂)|-|{x₂}|+|{v₂}|+|{u₁⁺}|≤t₂+1。

下面我们给出定理的证明：

建立

u for uÏV(C)

f(u)í u⁺ for uÎu₁C^®u₂^{- -}\{u₁⁺}

u for u=u₂^-

u⁺for uÎu₂⁺C^®v₂\{v₂}

u^-for uÎv₂⁺C^®u^-

从而有|N(x_i+1)ÈN(x)|≤n-(d(x_j+1)-|{x_j-1,x_j}|)-|{x_i+1,x}|≤n-d(x_j+1). ………（1）

显然N⁺_Cm(H) ÈV(H)中点和x_i+1,x_j+1均不相邻，则有|N(x_i+1)ÈN(x_j+1)|≤n-|N⁺_Cm(H) ÈV(H)|≤n- |N⁺_Cm(x)|-| V(H)|. ………（2）

d(x_i+1)≤n-(d(x_j+1)-|{x_j}|)-|{x_i+1}|-|V(H)|,有d(x_i+1)+d(x_j+1)≤n-|V(H)|, ………（3）

类似地，显然N⁺_Cm(x_j+1) ÈN_G-Cm(x_j+1) È{x}中点和x均不相邻，从而有

d(x)≤n-| N⁺_Cm(x_j+1) ÈN_G-Cm(x_j+1) È{x}|，有d(x)+d(x_j+1)≤n-1 ………（4）

显然，x_h-1和x的公共邻点只能在圈C_m上，所以有

|N(x_i+1)ÇN(x)|≤a-1. ………（5）

(i)若存在u,vÎS,使d(u)+d(v)≥n或|N(u)ÇN(v)|≥a。

(ii)若对任意S中的任意两点u,v均有|N(u)ÈN(v)|≥n-△(S)。

当S中的最大度点是x。

则由断言的（2），有|N(x_i+1)ÈN(x_j+1)|≤n-d(x)-1,和上面定理条件|N(u)ÈN(v)|≥n-△(S)矛盾。

当S中的最大度点在N⁺_Cm(H)中时。

我们分情况讨论如下：

情况1：| N_Cm(H)|≥3。

此时，记x_i1,x_i2,…,…x_i(_k_-1),x_i_kÎN_Cm(H)且要满足{x_i1+1,x_i1+2,…x_i2-1,x_i2+1,…x_i(_k_-1)-1,

若x_i_k_-1x_i_k₊₁ÏE(G)，则由断言的（1），将有|N(x_i(_k_-1)+1)ÈN(x)|≤n-(d(x_i_k₊₁)-|{x_i_k}|)-|{x_i(_k_-1)+1,

x_})≤n- d(x_i_k₊₁)-1,矛盾。

|N(x_i(h-1)+1)ÈN(x)|≤n-(d(x_ih+1)-|{x_ih-1,x_ih}|)-|{ x_i(h-1)+1,x}|-|{x_i_k₊₁}|≤n- d(x_ih+1)-1,矛盾。

当d(x_i_k_+t)＞max{d(x_it+1):t=1,2,…(k-1)}时。

情况2：| N_Cm(H)|=|{x_i,x_j}|=2。

断言(b):H的每一点都和x_i,x_j均相邻。否则，若H中有x和x_j不相邻，类似有|N(x_i+1)ÈN(x)|≤n- (d(x_j+1)-|{x_j}|-|{x_i+1,x}≤n- d(x_j+1)-1，矛盾。两断言正确。

子情况2.1：|V(H)|≥2.

记x_i,x_jÎN_Cm(H), |V(H)|=h,(I):若有x_kÎ{x_j+1,x_j+2,…x_i}和x_i+1相邻，也有x_k+rÎ{x_j+1,

x_j+2,…x_i}和x_j+1相邻(r是自然数，且认为x_k+1和x_i+1不相邻),则显然{x_k+1,x_k+2,…x_k+h}中点和x_j+1均不相邻（否则，因H 是完全子图，将有更长的圈）,

子情况2.2：|V(H)|=1.

记V(H)={x}，| N_Cm(x)|=|{x₁,x_h}|

其后，不妨认为d(x₂)≤d(x_h+1)。取S={x,x₂,x_h+1}.

我们断言(1)：x₂和x_h不相邻。否则，|N(x₂)ÈN(x)|=d(x₂)，由定理条件|N(x₂)ÈN(x)|≥n-△(S)=n-d(x_h+1)，得d(x₂)≥n-d(x_h+1)，与断言的（3）矛盾。

从而有d(x_t-1)+d(x_k-1)≤[n-d(x₂)-2]+[n-d(x_h+1)-2]=n-3。（*）

认为d(x_n-1)≤d(x_h-1)。

（1）断言：若x_k-1和x_h 相邻，则d(x_k-1)≥d(x_h-1)。否则，若d(x_k-1)<d(x_h-1)。从而定理条件，有d(x_n-1)+1=|N(x_n-1)ÈN(x)|≥n-△{x, x_n-1，x_k-1}

若d(x_k-1)≥d(x_n-1)_。则上面不等式d(x_n-1)+1=|N(x_n-1)ÈN(x)|≥n-△{x, x_n-1，x_k-1}= n- x_k-1)> n- d(x_h-1)_。与d(x_n-1)+d(x_h-1)=n-1，矛盾。

若d(x_k-1)<d(x_n-1)。则从而定理条件，有d(x_h-1)+1>d(x_k-1)+1=|N(x_k-1)ÈN(x)|≥n-△{x, x_n-1，x_k-1}= n- d(x_n-1)。与d(x_n-1)+d(x_h-1)=n-1，矛盾。

所以断言d(x_k-1)≥d(x_h-1)正确。

（2）类似有，若x_k-1和x_h 不相邻，则d(x_k-1)≥d(x_h-1)-1。

（4）类似有，若x_t-1和x_n 不相邻，则d(x_t-1)≥d(x_{n -1})-1。若x_k-1和x_h 相邻，或x_t-1和x_n 相邻。则d(x_k-1) +d(x_t-1)≥d(x_{n -1})+d(x_h-1)-1= n-2。与（*）矛盾。

所以，只能是：x_k-1和x_h 不相邻，及x_t-1和x_n 不相邻。得则d(x_k-1) +d(x_t-1)≥d(x_{n -1})+d(x_h-1)-2= n-3。结合（*），得d(x_k-1 )+d(x_t-1)= n-3。

则从而定理条件，有 d(x_k-1)+2=|N(x_k-1)ÈN(x)| ≥n-△{x, x_t-1，x_k-1}= n- d(x_t-1)，有n-3=d(x_k-1)+ d(x_t-1)≥n-2。矛盾。

至此，完成定理的证明。

参考文献

1、RJ Gould, Updating the Hamiltonian problem---a survey. J. Graph Theory 15 (1991), no. 2, 121—157

2、GA Dirac, Some theorems on abstract graphs, Proc. London Math.Soc.,2(1952) 69-81.

3、O Ore., Note on Hamiltonian circuits, Amer.Math.Monthly, 67 (1960), 55.

4、J A Bondy, V Chvátal, A method in graph theory. Discrete Math. 15 (1976), no. 2, 111--135.

5、V Chvátal, P Erdös, A note on Hamiltonian circuits. Discrete Math. 2 (1972), 111--113.

6、RJ Faudree, RJ Gould; MS Jacobson and RH Schelp, Neighborhood unions and Hamiltonian properties in graphs. J. Combin. Theory Ser. B 47 (1989), no. 1, 1--9.

7、RJ Faudree, RJ Gould; MS Jacobson, RH Schelp and L Lesniak, Neighborhood unions and highly Hamilton graphs,Ars Combinatoria,31(1991) 139-148.

8、G.H. Fan, New sufficient conditions for cycles in graphs, J.Combin.Theory Ser.B , 37 (1984), 221-227

9、Song Zengmin, Zhang Kemin, Neighborhood unions and Hamiltonian properties[J], Discrete Math., 133(1994) 319-324.

10、RJ Gould,Advances on the Hamiltonian problem—A survey[J], Graph and Combin. 19（2003）7-52. 121--157.

11、JA Bondy and USR Murty.,Graph theory with applications. Macmillan London ,New York,1976.是