下面发表在世界图论最权威杂志JCTb的泛圈图定理是18岁大学毕业、并在原北京大学分校现陕西理工大学2005年任副校长其后任正校长的张社民教授得到的（因做它的但不清楚就看一下这陕西理工大学见如陕西理工大学北京校友会会长张平院士、陕西理工大学北京校友会会长清华大学化学系教授李隽也多次候选院士、更有“总理李克强主持召开专家和企业家座谈会，苏剑、伍戈等专家和国家电力投资集团等企业负责人发了言”而第一个发言的苏剑也是陕西理工大学北京校友会会长,等等--看来这大学还是可以的。而这也算是18岁大学毕业的张社民校长做为陕西商州农村人在以前是不会有父母迫着读书的那这可说是天才还是因特殊爱好所致-可高考要考很多学科-谁能爱好那么多。当然早熟也非一切如华人唯一获得数学诺贝尔奖的丘成桐近18岁才读大学。如此张社民校长是我极佩服的数学专家之一，可在美国《数学评论》见天才的张校长2006年以前的几十年内也才仅有1篇论文-它就是下面我再给出简单证明的--这说明这世界三大难题之一的哈密顿图泛圈图非常不容易、也说明以前不容易。而且从我已竭尽全力的下面再证明中感到已极难创造出更好的技术理论方法等去给出这定理更好的证明

Short proof of well-known theorem on pancyclic graphs

Kewen Zhao

Department of Mathematics, Qiongzhou University, Wuzhishan, Hainan, 572200, P. R. China

Abstract: In 1994, Zhang proved the following well-known theorem: “Let G be a Hamiltonian graph of order n. If there exists a vertex x such that d(x)+d(y)≥n for each y not adjacent to x, then G is pancyclic or K_{n/2,n/2” [J. Combin. Theory Ser. B 60 (1994), 2, 159-168]. In this note, we give a simple proof of the theorem}

In this paper, we consider only finite, undirected graph without loops or multiple edges. For a vertex u in G, we denote N(u)={v: uvÎE(G)} and G[N(u)] the subgraph induced by N(u) in G.. Let C_m=x₁x₂…x_mx₁ denote a cycle of order m. Others notation can be found in [1].

In 1994, Zhang [3] proved the following well-known theorem:

Theorem. Let G be a Hamiltonian graph of order n. If there exists a vertex x such that d(x)+d(y)≥n for each y not adjacent to x, then G is pancyclic or K_n/2,n/2.

Now we show a simple proof of the above theorem.

Proof. Let C_n=x₁x₂…x_nx₁ be a Hamiltonian cycle of G,. We consider the following three cases.

Case 1. x₁x₃ÎE(G).

In this case, G has C₃. If G does not have C_j, j≥4, then x₁x_jÏE(G), and when x_i is adjacent to x₁, then x_i+1 is not adjacent to x_j for i+1≤j-1(if x_i+1x_jÎE(G), we have C_j=x₁x_i+1x_i+2…x_jx_ix_i-1…x₁, a contradiction) or x_i is not adjacent to x_j for i≥j+1. Otherwise, we have C_j=x₁x₃x₄…x_jx_ix₁. Hence we can check that d(x_j)≤n-d(x₁)-|{x_j}|, this implies d(x₁)+d(x_j)≤n-1, which contradicts the assumption of Theorem. The contradiction shows that G has C_j, j=4, 5,…,i+1. Thus, G is pancyclic.

Case 2. x₁x₃ÏE(G) and x₁x₄ÎE(G).

We consider the following. (i) When x₁ is adjacent to some consecutive x_i,x_i+1. If G does not have C_j, then x₁x_jÏE(G). (i-1) When i+1≤j-1, x_jx₂ÏE(G) (Otherwise, we have C_j=x_jx₂x₃…x_ix₁x_i+1…x_j). Then for any x_r, if x₁x_rÎE(G), then x_r-1x_jÏE(G) for r≤j-1, or x_r-1x_j,x_r+1x_jÏE(G) for r≥j+1( Otherwise, by x₁x₄ÎE(G), we easily get C_j). Hence we can check that d(x_j)≤n-d(x₁)-|{x₂}|, a contradiction. (i-2) When j+1≤i, then x_jx_i-1,x_jx_i,x_jx_i+1,x_jx_i+2ÏE(G). Hence d(x₁)+d(x_i)≤n-1, a contradiction. So we have C_j，j=5, 6,…n. And x₁ is adjacent to x_i,x_i+1 and x₁x₄ÎE(G), so we also have C₃, C₄ , i.e., G is pancyclic.

(ii) When N(x₁)∩{x_h,x_h+1…x_i}={x_h,x_i}, i≥h+3. If G does not have C_j, then x₁x_jÏE(G). (ii-1) When h+2≤j, then x_jx_h+1 or x_jx₂ or x₁x_j-1ÏE(G)( Otherwise, C_j=x_jx_h+1x_h+2…x_j-1x₁x_hx_h-1…x₂x_j), and by similar argument of (i), we have d(x₁)+d(x_j)≤n-1, a contradiction. (ii-2) When i-2≥j, then we have x_jx_i-1,x_jx_i+1ÏE(G). And by similar argument of (i), we have d(x₁)+d(x_j)≤n-1, a contradiction. So G has C_j, j=5, 6,…n. Then when d(x₁)≥n/2, x₁ must be adjacent to consecutive x_i,x_i+1, so G has C₃; when d(x₁)<n/2, by d(x₁)+d(x_j)≥n, d(x_j)>n/2, so x_j must be adjacent to consecutive x_r,x_r+1, so G has C₃, thus G is pancyclic.

(iii). G is the case without (i) and (ii). In this case, clearly, d(x₁)=n/2 and N(x₁)={x₂,x₄,x₆,x₈,x₂,x₃,…x_2m,x_2m+2,…x_n-2,x_n}，so G has all even cycles. If G[N(x₁)] or G-N(x₁) has a edge, then G also has all odd cycles, i.e., G is pancyclic; if G[N(x₁)] and G-N(x₁) has not edge, together with the assumption of Theorem, this implies G=K_n/2,n/2.

Case 3. x₁x₃ÏE(G), x₁x₄ÏE(G).

Without loss of generality, assume the most close vertex of x₁ along C_n, except x₂ and x_n, is x_i(it is said that x₃,x₄…,x_i-1 and x_n-1,x_n-2…,x_n-(i-3) are not adjacent to x₁). For any j, if G does not have C_j, by similar argument of Case 1, x_jx_j-2ÏE(G). We also have x₁x_j-1 or x_jx₃ or x_jx₂ÏE(G)( otherwise, C_j=x_jx₃x₄…x_j-1x₁x₂x_j). And if x_ix₁ÎE(G), then x_i+1x_j,ÏE(G) for i+1≤j-1, or x_ix_jÏE(G) for j+1≤i. Hence we have d(x₁)+d(x_i)≤n-1, a contradiction. Thus, when j≥i, G has C_j, j=i,i+1,…n. When j≤i-1, by d(x₁)+d(x_j)≥n, both x₁,x_j have a common neighborsÏ{x₃,x₄…,x_i-1}, so G has C_j+1, j=3, 4,…,i-1. Again, since N(x₁)∩{x₂,x₃,x₄}={x₂}, by similar argument of (ii) of Case 2, G has C₃, so G is pancyclic.

References

1. J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, Macmillan, London and Elsevier,New York, 1976.

2. R. J. Gould, Advances on the Hamiltonian problem—a survey. Graphs Combin. 19 (2003), 1, 7--5

3. S. M. Zhang, Pancyclism and bipancyclism of Hamiltonian graphs. J. Combin. Theory Ser. B 60 (1994), 2, 159--168.

附注：Gould主席的著名综述文章“Advances on the Hamiltonian problem—a survey. Graphs Combin. 19 (2003), 1, 7--52”的参考文献中收录246篇论文，但只收录118个重要定理，上面复印件中张社民教授的定理是定理116，可见张社民校长这定理值得寻找好的证明。

我们重视它是除了张教授这篇论文很有价值常被国外引用外，这篇论文最后也说得到我国顶级领军人物田丰教授和管梅谷校长的意见和评注。因田、管这2先生当时分别是中国图论学会秘书长和主席，特别是张社民教授1984年跟这我国首批博士导师、世界大师管梅谷读研究生，而在张社民读研究生期间神一般的Erdös和美国科学院副院长Graham等就被管梅谷教授邀请来该大学做报告，如此抱负和视角一定是世界级的（要知道这学科很不容易如各权威的论文都很少也如在美国《数学评论》见张社民教授2006年以前仅有一篇论文--它就是这上面论文--可见价值）

为了探索尽可能多种最优方法，这里是我取得很大突破的若干著名方法备忘录：1、Whitney定理即“惠特尼定理” ；2、Bondy,定理；3、Bollobás定理；4、Faudree定理；5、Bermond定理；6、Linial定理；7、Hajnal定理；8、Kronk 定理；9、获得全国18项科技一等奖(数学唯一一项一等)的组合矩阵论中《中国科学》发表的柳-邵定理；10、范理事长的定理；11、邵理事长的定理 12、陈定理；13、海南的推广定理；14、宋理事长的定理；15、原北京大学分校张校长的定理，等等，当然并非简短的证明才值得学习，200页的证明虽头痛但很多方法可总结，我每次体会它们总有新的感想

下面发表在图论的世界权威杂志JCTb的二分图定理是18岁就已大学毕业、并是原北京大学分校现陕西理工大学正副校长、党委书记中唯一有博士学位的张社民校长得到的，但他的证明非常复杂，如此我下面6行字就证明（18岁大学毕业这在以前是天才，如陈后华人第一数学大师丘成桐近18岁才读大学。可在美国《数学评论》见天才的张校长2006年以前也仅有1篇论文，可见哈密顿图之艰难--如他这唯一论文的被我下面六行字证明的结果就不易-有些人要经百次、千次、有些万次失败--可能没想到这六行字会有上万次选择的可能吧？而许多接近正确的错误排除一次都不容易

1. Gould主席的著名综述文章“Advances on the Hamiltonian problem—a survey. Graphs Combin. 19 (2003), 1, 7--52”的参考文献中收录246篇论文，但只收录118个重要定理，上面复印件中张社民教授的定理是定理117

2. 张社民教授对上面定理的证明共引用3个引理，其中之一是上面较复杂的引理4.2（Lemma 4.2）（较复杂也如张社民教授在论文中陈述这一引理就用9行字，而我上面对定理的证明却仅用6行字）。

也就是我上面仅用六行字就证明张社民教授的上面定理且不需要引用任何引理（也就六行证明Gould主席的上面综述文章中的定理117）。重视它是因张教授这篇论文很有价值常被国外引用，而且这篇论文最后也说得到田丰教授和管梅谷教授的意见和评注--那就应更受重视。因田、管这2先生当时分别是中国图论学会秘书长和主席，特别是张社民教授1984年跟这我国首批博士导师、世界大师管梅谷读研究生，而在张社民读研究生期间神一般的Erdös和美国科学院副院长Graham等就被管梅谷教授邀请来做报告，如此视角一定是世界级的（要知道这学科很不容易如各权威的论文都很少也如在美国《数学评论》见张社民教授2006年以前仅有一篇论文--它就是上面论文--可见价值）

可参考二分图专著：Bipartite Graphs and their Applications，此书3个作者Armen Asratian于1980年获得莫斯科大学博士，Tristan. Denley现任美国Austin Peay州立大学常务校长，Roland Häggkvist于1977年获得Dirac的博士。其实象我们大学毕业于图论的研究生林越等老师都能知道六行字就证完的关键在哪？

为了探索尽可能多种最优方法，这里是我取得很大突破的若干著名方法备忘录：获得国家奖的范定理、Whitney定理、1991年《中国科学》发表的柳-邵定理、陈定理、L猜想、宋理事长的宋定理、Bondy,定理、Bermond定理、Linial定理、海南省最重要的黄定理，等等，当然并非简短的证明才值得学习，200页的证明虽头痛但很多方法可总结，我每次体会它们总有新的感想

1. Gould主席的著名综述文章“Advances on the Hamiltonian problem—a survey. Graphs Combin. 19 (2003), 1, 7--52”的参考文献中收录246篇论文，但只收录118个重要定理，上面复印件中张社民教授的定理是定理117

2. 上面张社民教授证明的上面定理共引用3个引理，其中之一是上面较复杂的引理4.2（Lemma 4.2）（较复杂是这引理在张社民教授的论文中也是九行字，而我上面对定理的证明仅六行字）它是加州最悠久的圣何塞州立大学Edward Schmeichel教授和这里第2段说80年代是系主任的John Mitchem合作的论文Bipartite graphs with cycles of all even lengths. J. Graph Theory 6 (1982), 4, 429-439中的非常复杂的结果。

我上面仅用六行字证明张社民教授的上面定理且不引用一个引理（也就证明Gould主席的综述文章中的定理117），但我想哈密顿图专家看了我的六行会清楚要想出这途径不易。我的众多工作都与200页的突破的众多方法等的艰难积累、与各位老师、各位合作专家以及众多相关专家的帮助某种关系。因为这篇论文最后说得到田丰教授和管梅谷教授的意见和评注，而这2人当时分别是中国图论学会秘书长和主席，特别是张社民教授1984年跟我国首批博士导师、世界大师管梅谷读研究生，而在张社民读研究生期间神一般的Erdös和美国科学院副院长Graham等就被管梅谷教授邀请来做报告（可这学科很难如各权威的论文都很少也如2006年前美国《数学评论》仅收录张社民教授仅一篇论文却就是上面定理的国外SCI论文，可见名师的研究生就有别人所不及，张教授仅做2篇图论论文但全都哈密顿图的）

为了探索多种最优方法，这里是我取得突破很大的若干著名方法备忘录：：1、Whitney定理即“惠特尼定理” ；2、Bondy,定理；3、Bollobás定理；4、Faudree定理；5、Bermond定理；6、Linial定理；7、Hajnal定理；8、Kronk 定理；9、获得全国18项科技一等奖(数学唯一一项一等)的组合矩阵论中《中国科学》发表的柳-邵定理；10、范理事长的定理；11、邵理事长的定理 12、陈定理；13、海南的推广定理；14、宋理事长的定理；15、原北京大学分校张校长的定理，等等，当然并非简短的证明才值得学习，200页的证明虽头痛但很多方法可总结，我每次体会它们总有新的感想