下面发表在图论重要杂志JCTb泛圈图定理是18岁就已大学毕业、并是原北京大学分校陕西理工大学正副校长、党委书记中当时唯一具有博士学位的张社民校长得到的(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 Kn/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 Cm=x1x2…xmx1 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 Kn/2,n/2.  

Now we show a simple proof of the above theorem.

Proof. Let Cn=x1x2…xnx1 be a Hamiltonian cycle of G,. We consider the following three cases.

Case 1. x1x3ÎE(G).

In this case, G has C3. If G does not have Cj, j4, then x1xjÏE(G), and when xi is adjacent to x1, then xi+1 is not adjacent to xj for i+1j-1(if xi+1xjÎE(G), we have Cj=x1xi+1xi+2…xjxixi-1…x1, a contradiction) or xi is not adjacent to xj for ij+1. Otherwise, we have Cj=x1x3x4…xjxix1. Hence we can check that d(xj)n-d(x1)-|{xj}|, this implies d(x1)+d(xj)n-1, which contradicts the assumption of Theorem. The contradiction shows that G has Cj, j=4, 5,,i+1. Thus, G is pancyclic.

Case 2. x1x3ÏE(G) and x1x4ÎE(G). 

We consider the following. (i) When x1 is adjacent to some consecutive xi,xi+1. If G does not have Cj, then x1xjÏE(G). (i-1) When i+1j-1, xjx2ÏE(G) (Otherwise, we have Cj=xjx2x3…xix1xi+1…xj). Then for any xr, if x1xrÎE(G), then xr-1xjÏE(G) for rj-1, or xr-1xj,xr+1xjÏE(G) for rj+1( Otherwise, by x1x4ÎE(G), we easily get Cj). Hence we can check that d(xj)n-d(x1)-|{x2}|, a contradiction. (i-2) When j+1i,  then xjxi-1,xjxi,xjxi+1,xjxi+2ÏE(G). Hence d(x1)+d(xi)n-1, a contradiction. So we have Cjj=5, 6,n. And x1 is adjacent to xi,xi+1 and x1x4ÎE(G), so we also have C3, C4 , i.e., G is pancyclic.

(ii) When N(x1){xh,xh+1…xi}={xh,xi}, ih+3. If G does not have Cj, then x1xjÏE(G). (ii-1) When h+2j, then xjxh+1 or xjx2 or x1xj-1ÏE(G)( Otherwise, Cj=xjxh+1xh+2…xj-1x1xhxh-1…x2xj), and by similar argument of (i), we have d(x1)+d(xj)n-1, a contradiction. (ii-2) When i-2j, then we have xjxi-1,xjxi+1ÏE(G). And by similar argument of (i), we have d(x1)+d(xj)n-1, a contradiction. So G has Cj, j=5, 6,n. Then when d(x1)n/2, x1 must be adjacent to consecutive xi,xi+1, so G has C3; when d(x1)<n/2, by d(x1)+d(xj)n, d(xj)>n/2, so xj must be adjacent to consecutive xr,xr+1, so G has C3, thus G is pancyclic.

(iii). G is the case without (i) and (ii). In this case, clearly, d(x1)=n/2 and N(x1)={x2,x4,x6,x8,x2,x3,…x2m,x2m+2,…xn-2,xn}so G has all even cycles. If G[N(x1)] or G-N(x1) has a edge, then G also has all odd cycles, i.e., G is pancyclic; if G[N(x1)] and G-N(x1) has not edge, together with the assumption of Theorem, this implies G=Kn/2,n/2.

Case 3. x1x3ÏE(G), x1x4ÏE(G).

Without loss of generality, assume the most close vertex of x1 along Cn, except x2 and xn, is xi(it is said that x3,x4…,xi-1 and xn-1,xn-2…,xn-(i-3) are not adjacent to x1). For any j, if G does not have Cj, by similar argument of Case 1, xjxj-2ÏE(G). We also have x1xj-1 or xjx3 or xjx2ÏE(G)( otherwise, Cj=xjx3x4…xj-1x1x2xj). And if xix1ÎE(G), then xi+1xj,ÏE(G) for i+1j-1, or xixjÏE(G) for j+1i. Hence we have d(x1)+d(xi)n-1, a contradiction. Thus, when j≥i, G has Cj, j=i,i+1,…n. When j≤i-1, by d(x1)+d(xj)≥n, both x1,xj have a common neighborsÏ{x3,x4…,xi-1}, so G has Cj+1, j=3, 4,…,i-1. Again, since N(x1){x2,x3,x4}={x2}, by similar argument of (ii) of Case 2, G has C3, 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年以前仅有一篇论文--它就是这上面论文--可见价值)

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

 

 

 

 

 

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

未标题-1

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

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

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

可参考二分图专著:Bipartite Graphs and their Applications,此书3个作者Armen Asratian1980年获得莫斯科大学博士,Tristan. Denley现任美国Austin Peay州立大学常务校长Roland Häggkvist1977年获得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.2Lemma 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篇图论论文但全都哈密顿图的)

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