On k-path Hamiltonian graphs, neighborhood union conditions and degree sum conditions involving distance two

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

Abstract: In 1969, Kronk investigated the k-path Hamiltonian using nonadjacent vertices. In this present paper, we investigate the k-path Hamiltonian path using nonadjacent vertices involving distance.

（注：我们改进的这个K-path hamiltonian graphs结果主要由指导许多博士门徒成了计算机大师（如既有“现代计算机之父”，又有“计算机之母的耶鲁大学Ore院士评审决定

In 1969, Kronk proved the following Theorem 1 [1] on k-Hamiltonian graphs.

Theorem 1(Kronk [1]). If G is a connected graph with n vertices and d(u)+d(v)≥n+k for each pair of distinct nonadjacent vertices u,v in G, then G is k-path Hamiltonian.

(定理1 (Kronk [1]).n阶图G不相邻的任意两点x,y均有d(x)+d(y)≥n+k，则Gk-path哈密顿图）

In this present paper, we generalize k-path Hamiltonian path involving distance as follows.

Theorem 2. If G is a 2-connected graph with n vertices and d(u)+d(v)≥n-1+k for each pair of distinct non-adjacent vertices u,v of d(u,v)=2 in G, then G is k-path Hamiltonian path.

(定理2. n阶图G距离为2的任意两点x,y均有d(x)+d(y)≥n+k，则Gk-path哈密顿路）

To prove Theorem 2, we need the following four lemmas of Erdös [4], Paul Erdös,Tibor Gallai[6]Gallai的导师Kőnig的导师闵可夫斯基是爱因斯坦的老师并对其相对论的发展又很大影响Gallai的博士是获得3次国际数学奥林匹克竟赛金奖的国际数学联盟主席）, Zhao, Lai, [11].

Lemma 1(Zhao-Lai-Shao [11]). If G is a connected graph with n vertices and d(u)+d(v)≥n-1 for each pair of distinct non-adjacent vertices u,v of d(u,v)=2 in G, then G has Hamiltonian path.

Lemma 2(Zhao-Lai-Shao [11]). If G is a 2-connected graph with n vertices and d(u)+d(v)≥n for each pair of distinct non-adjacent vertices u,v of d(u,v)=2 in G, then G is Hamiltonian.

Lemma 3. (Paul Erdös [4].) G has a Hamiltonian circuit if every vertex of G has valency at least k, where either k ³n/2, or k<n/2 and G has at least f(n, k) edges, where f(n, k)=max {(n-k2)+k2+1, ([(n+2)/2]2) +[(n-1)/2]2+1}, (This bound on the number of edges is the least possible, again in

Lemma 4. (Paul Erdös, Tibor Gallai([6], Theorem (2.7)).) Let G be aundirected graph on n vertices with at least d{n- 1)/2 + 1 edges, where d > 1.Then G contains a circuit of length at least d+l

The Proof of Theorem 2.

By d(u)+d(v)≥n-1+k for each pair of distinct non-adjacent vertices u,v of d(u,v)=2, and d(u) ≤n-|{u,v}|=n-2 for each pair of distinct non-adjacent vertices u,v of d(u,v)=2, we have d(v) ≥n-1+k-d(u)≥k+1 for each vertex v in G.

Let Pk=x0x1¼xk be a path of length k in G, we shall prove the following two claims.

Claim 1. G-Pk\{xo} is connected.

Claim 2. G-Pk has at most two components and if G-Pk has two components H, T, then H and T are two Hamiltonian subgraphs and there exist some vertex of H and some vertex of T that they are all adjacent to x0 and xk .

Proof of Claim 1. If H, and T be two components of G-Pk\{xo} (i). If there exists a vertex of Pk\{xo}=x1x2¼xk that is adjacent to at least a vertex of H and adjacent to at least a vertex of T, then there exist x in H and y in T with d(x,y)=2. We can check that d(x)+d(y)≤2|V(Pk\{xo})|+|V(H)|+|V(T)|-|{x,y}|≤n+k-3, which contradicts the hypothesis of Theorem. (ii). If each vertex of Pk\{xo}=x1x2¼xk is not adjacent to any vertex of at least one of {H, T}. Without loss of generality, assume xh of Pk\{xo} is not adjacent to any vertex of H and xh-1 is adjacent to some vertex x of H, then we can check that d(x)+d(xh) ≤(k+|V(H)\{x}|)+(k-1+|V(T)|≤n+k-2, a contradiction.

Proof of Claim 2. If H, T and Q be three components of G-Pk. (i). If there exists a vertex of Pk=x0x1¼xk that is adjacent to at least a vertex of H and adjacent to at least a vertex of T, then there exist x in H and y in T with d(x,y)=2. We can check inequality (1): d(x)+d(y)≤2(k+1)+|V(H)|+|V(T)|-|{x,y}|≤n-|V(Q)|+k-1, a contradiction. (ii). If each vertex of Pk=x0x1¼xk is at most adjacent to some vertices of one of {H, T, Q}. Without loss of generality, assume xh is not adjacent to any vertex of H and xh-1 is adjacent to some vertex x of H, then we can check that d(x)+d(xh) ≤(k+1+|V(H)|)+(k+1+max{|V(T)|, |V(Q)|})-|{x,xh}|≤n+k-2, a contradiction. Thus, G-Pk has at most two components H, T. so completing the proof of Claim 2.

Now, we consider the following cases.

Case 1. G-Pk has two components H, T.

By d(u)+d(v)≥n-1+k for each pair of distinct non-adjacent vertices u,v of d(u,v)=2 in H, we have dH(u)+dH(v)≥n-1+k-2(k+1)≥n-(k+1)-|V(T)|-1=|V(H)|-1. Lemma 1, H and T have Hamiltonian path. Let y1y2¼y|V(H)| be a Hamiltonian path of H and z1z2¼z|V(T)| be a Hamiltonian path of T. By Claim 1 that G-Pk\{xo} is connected, so there must exist yh in H and zr in T that are adjacent to some vertex of Pk=x0x1¼xk. By the hypothesis of Theorem that d(yh)+d(zr)≥n-1+k, so d(yh)+d(zr)=[dPk(yh)+dH(yh)]+[dPk(zr)+dT(zr)]≥n-1+k, this implies dPk(yh)=k+1, dH(yh)=|V(H)|-|{yh}|, dPk(zr)=k+1, dT(zr)=|V(T)|-|{ zr}|, so yh is adjacent to x0 and y1. By d(x0)+d(y1)≥n-1+k, there must exist yi in Hamiltonian path y1y2¼y|V(H)| of H satisfying that y1 is adjacent to yi  and x0 is adjacent to yi-1(The reason is similar to the above).  Similarly, there must exist zj in Hamiltonian path z1z2¼z|V(T)| of T satisfying that z1 is adjacent to zj and xk is adjacent to yj-1. Since yi-1 is a end-vertex of Hamiltonian path yi-1yi-1¼y1 yiyi+1¼y|V(H)| of H and zj-1 is a end-vertex of Hamiltonian path zjzj-1¼z1zjzj+1¼z|V(T)| of T, so completing the proof.

Next, by d(u)+d(v)≥n-1+k for each pair of distinct non-adjacent vertices u,v of d(u,v)=2 in G, we can check that dG-Pk(u)+dG-Pk(v)≥n-1+k-2|V(Pk)|≥n-1+k-2(k+1)=(n-k-1)-2 for each pair of distinct non-adjacent vertices u,v of d(u,v)=2 in G-Pk, so G-Pk has a path of length at least |V(G-Pk)|-1. We consider the following.

Case 2. G-Pk is connected..

We consider the following two subcases.

Subcase 2.1. G-Pk has a Hamiltonian path.

Let P=y1y2¼yn-k-1 be a Hamiltonian path of G-Pk. Since d(u)≥k+1 for each vertex u in G, so x0,xk are all adjacent to at least one vertex of G-Pk. We claim that there exist two distinct vertices yi,yj that are adjacent to x0,xk, respectively (Otherwise, it is said that x0,xk are all only adjacent to a vertex yr of G-Pk.. In this case, clearly, |N(x0)|≤|V(Pk)\{x0}|+|{yr}|=k+1 and |N(yr+1)||V(G)\{x0,xk,yr+1}|=n-3, so we can check that d(x0)+d(yr+1)(k+1)+|V(G)\{x0,xk ,yr+1}|n-2+k, a contradiction ). Without loss of generality, assume yi is adjacent to x0,and yj is adjacent to,xk and let i,j be as small as possible, so both yi-1,and yj-1 are all not adjacent to x0,xk. Without loss of generality, assume i≤j-1.

If i=j-1, clearly, the proof is complete.

If i≤j-2. We consider

By d(yi-1)+d(x0)≥n-1+k and d(yj-1)+d(xk)≥n-1+k, and yi-1,and yj-1 are all not adjacent to x0,xk, we have dG-Pk(yi-1)+dG-Pk(x0)≥n-1+k-(k+k-1)=n-k and dG-Pk(yj-1)+ dG-Pk(xk)≥n-1+k-(k+k-1)=n-k, so we have dG-Pk(yi-1)+dG-Pk(yj-1)≥n-k or dG-Pk(x0)+ dG-Pk(xk)≥n-k. We consider the following two cases.

(1). If dG-Pk(yi-1)+dG-Pk(yj-1)≥n-k.

In this case, we have the following. (i). When ytÎNP(yj-1)∩{yj,yj+1,¼,yn-k}\{yj}, then yt-1 is not adjacent to yi-1( Otherwise, if yt-1 is adjacent to yi+1, then the path yiyi+1¼ yj-1ytyt+1¼yn-k and the path yjyj+1¼ yt-1yi-1yi-2¼ y1 partitioned from P that their end-vertices yi(=x0) and yj  are adjacent to x1,xk, respectively, a contradiction). (ii). When ytÎNP(yj-1)∩{yi,yi+1,¼,yj-1}, then yt+1 is not adjacent to yi-1. (iii). When ytÎNP(yj-1)∩{y1,y2,¼,yi-1}, then yt-1 is not adjacent to yi-1. Also, clearly yi-1 is belongs to neither any yt+1 of (ii) nor any yt-1 of (iii). So we can check that dP(yi-1) ≤|V(G-P*)|-|NP(yj-1)\ {yj}|-|{yi-1}|≤(n-k-1)-|NP(yj-1)\ {yj}|-|{yi-1}|, this implies dG-Pk(yi-1)+dG-Pk(yj-1)≤n-k-1, a contradiction.

(2). If dG-Pk(x0)+dG-Pk(xk)≥n-k-1.

In this case, if x0 or xk is adjacent to y1 or yn-k-1, then we complete the proof. If x0 and xk are not adjacent to y1 and yn-k-1, then clearly, there must exist consecutive two vertices yh and yh+1of P that they are adjacent to x0,xk, respectively, so completing the proof.

Subcase 2.2. G-Pk has not any Hamiltonian path.

Therefore, The proof is complete.

Theorem 3 (Kapoor, Theckedath, 1971). If G is a connected graph with n vertices and d(u)+d(v)≥n-1+k for each pair of distinct non-adjacent vertices u,v in G, then G is k-path Hamiltonian path.

(定理3. n阶图G不相邻的任意两点x,y均有d(x)+d(y)≥n-1+k，则Gk-path哈密顿路-此定理见[3]

Proof. Let Pk=x0x1¼xk be a path of length k in G. By d(u)+d(v)≥n+k for each pair of nonadjacent vertices u,v in G, dH(u)+dH(v)≥n+k-2|V(Pk)\{xo}|≥n+k-2k=n-k, so H=G-(Pk\{xo}) is connected. By Lemma 2, H has Hamiltonian cycle. Let T=y1y2¼yn-k y1 be a Hamiltonian cycle of G-Pk\{xo}, if H=G-(Pk\{xo}) has Hamiltonian cycle or xk is adjacent to one of {y1,yn-k}, the proof is complete. Otherwise, y1yn-kÏE(G) and xk is not adjacent y1,yn-k, we have dT(y1)+dT(yn-k)≥n-1+k-2(k-1)=n-k+1. Since |G-(Pk\{xo})|=n-k, so there must exist consecutive vertices yh,yh+1 that are adjacent to yn-1,y1, respectively. So H=G-(Pk\{xo}) has Hamiltonian cycle, a contradiction.

A digraph D of order p is of Ore-type (k) if od(u) + id(u) p + k whenever u and v are distinct vertices for which uv is not an arc of D.. And a digraph D of order p is of Ore-type2 (k) if od(u) + id(u) p + k whenever u and v are distinct vertices for which d(u,v)=2 .

John Roberts ontained the following result in [3].

Theorem 4. If a nontrivial digraph D is of Ore-type (k), k > 0, then D is k-path hamiltonian.

We conjecture that

Conjecture. If a nontrivial digraph D is of Ore-type2 (k), k > 0, then D is k-path hamiltonian.

（对哈密顿图有时几行字都很不容易，象这里的张校长的几行字都要求得到这两个中国最利害的大师提供的帮助和意见等，这里的几行字更是照耀中国光耀世界

References

1 Hudson Kronk, A note on k-path Hamiltonian graphs. J. Combinatorial Theory 7 1969, 104–106.

2 Kenneth Reid, Carsten Thomassen, Edge sets contained in circuits. Israel J. Math. 24 (1976), no. 3–4, 305--319.

3.John Roberts, A sufficient condition for k-path Hamiltonian digraphs. Bull. Amer. Math. Soc. 82 (1976), no. 1, 63--65.

4Paul Erdös 'Remarks on a paper of P6sa', Magyar Tud. Akad. Mat. Kutatd Int.Kozl. 7 (1962) 227-229.

5Paul Erdös'Unsolved problems in graph theory and combinatorial analysis', inCombinatorial mathematics and its applications (Proc. I.M.A. Conference,Oxford, July 1969), ed. D. J. A. Welsh (Academic Press, London, 1971),97-109.

6Paul ErdösTibor GallaiOn maximal paths and circuits of graphs', Acta Math.Acad. Sci. Hungar. 10 (1959) 337-359.

7Günter Schaar, On k-path traceable graphs. Journal of Information Processing and Cybernetics 24 (1988), no. 1-2, 19--30.（此杂志现名Journal of Automata, Languages and Combinatorics-即《自动机、语言与组合学杂志》--主编是1972年获博士学位、1987年任计算机领域曾多次排名德国第一马格德堡大学计算机系教授的世界大师Jürgen Dassow

8D. R. Woodall, Sufficient conditions for circuits in graphs, Proc. London Math. Soc. (3) 24 (1972), 739-755.

9Ilker Baybars, On k-path Hamiltonian maximal planar graphs. Discrete Math. 40 (1982), no. 1, 119--121.

10Crispin Nash-Williams, 'On Hamiltonian circuits in finite graphs', Proc-Amer. Math. Soc. 17 (1966) 466

11 Kewen Zhao, Hongjian Lai, Yehong Shao, New sufficient condition for Hamiltonian graphs. Appl. Math. Lett. 20 (2007), no. 1, 116--122.

12德国多特蒙德工业大学终身教授、罗马尼亚科学院院士Tudor Zamfirescu（他的博士有苑立平副院长中华全国青年联合会第十一届委员）, On  Boll. Un. Mat. Ital. (4) 6 (1972), 61--66.

13Tudor Zamfirescu院士On k-path hamiltonian graphs and line-graphs. Rend. Sem. Mat. Univ. Padova 46 (1971), 385--389.（看庆贺他的70岁的学术会议见许多著名数学家的相片-有他和Solomon Marcus院士，Imre Bárány院士，János Pach院士，还有前辈级名家Rolf SchneiderWlodzimierz Kuperberg，以及最近接连获大奖的Karim Adiprasito特别是他最近和June Huh, Eric Katz合作在 Notices Amer. Math. Soc. 发表论文Hodge theory of matroids 64 (2017), no. 1, 26–30简概”并引起广泛的国际反响，在很多网站都有Karim Adiprasito, June Huh, Eric Katz的这工作Hodge theory for combinatorial geometries发表在Ann. of Math. (2) 188 (2018), no. 2, 381–452的详细全文

14RichardDaltonk-arc Hamilton graphs.Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), pp. 545--556, Lecture Notes in Math., 642, Springer, Berlin, 1978.

15Kewen Zhao, Hongjian Lai, Ju Zhou, Hamiltonian-connected graphs. Comput. Math. Appl. 55 (2008), no. 12, 2707--2714.

To prove Theorem 5, we need the following two lemmas by Zhao [15].

Lemme 2. If the connectivity of graph G of order n≥3 is 1, and if |N(x)N(y)|≥n-d-2 for each pair of nonadjacent vertices x,y of d(u,v)=2 in G, then G is (Kh# K1#Kn-h-1).

Where Kh and Kn-h-1 are two disjoint complete graphs of orders h and n-h-1, respectively, and u=V(K1) is a cut vertex of G, and the vertex set of G to be V(Kh# K1#Kn-h-1)=V(Kh)V(Kn-h-1){u}, the edge set of G to be E(Kh# K1#Kn-h-1)=E(Kh)E(Kn-h-1)e*, e* is an edge set of cut vertex u connected to some vertices of Kn-h-1 and some vertices of Kh.

Proof. Let u be a cut vertex of G. We claim that G-u has only just two components denoted by H, T and they are two complete subgraphs. Otherwise, if H is not complete subgraph, let x,yÎV(H) with d(x,y)=2, and w is any a vertex of T, then we can check that |N(x)N(y)|≤|V(G)|-|{x,y}|-|V(T)| ≤n-2-(d+1) ≤n-3- d, a contradiction. Thus, H is complete subgraph. Similarly, we can prove that each component of G-u is complete subgraph. Furthermore, if G-u has three components H, T and Q, then, let x,y be two vertices that are adjacent to cut vertex u and belong to H, T, respectively. Then similarly, we can check that |N(x)N(y)|≤|V(G)|-|{x,y}|-|V(Q)| ≤n-2-(d+1) ≤n-3- d, a contradiction.

The proof of Theorem 5.

let P*=x0x1¼xk be a path of length k in G. By |N(x)N(y)|≥n-d+k for any two vertices x,y in G with d(x,y)=2 and since d£d(G-P*)+|V(P*)|, where H=G-P*, we have inequality (*): |NH(x)NH(y)|≥n-d+k-|V(P*)|=(|V(G-P*)|+|V(P*)|)-(d(G-P*)+|V(P*)|)+k-|V(P*)|=|V(G-P*)|-d(G-P*)-1 for any two vertices x,y in H=G-P* with dG(x,y)=2. Then we consider the following.

Claim that if H=G-P* is not connected, then H has at most two components and each component of H is complete subgraph.

Otherwise, if Q and T are two components of G-P* with that T is not complete. So, without loss of generality, assume x, y are two vertices of T with d(x,y)=2, then we can check that |NH(x)NH(y)|≤|V(T)|-|{x,y}|≤|V(G-P*)|-|V(Q)|-|{x,y}|≤|V(H)|-d(H)-2, which contradicts inequality (*). So each component of H is complete. If H has at least three components Q, T, R. (i). If there exist vertex x in Q and y in T with d(x,y)=2, we can check that |NH(x)NH(y)|≤|V(Q)|+|V(T)|-|{x,y}|≤|V(H)|-|V(R)|-|{x,y}|≤|V(H)|-d(H)-2, which contradicts the above inequality (*).

(ii). If there do not exist two vertices of that their distance is 2. Without loss of generality, we may assume that xj of P* is adjacent to some vertex y of Q, and xj+1 is not adjacent to y. Then clearly, xj+1 is not adjacent to every vertex of one of {T,R}. Hence we can check that |NH(xj+1)NH(y)|≤|V(Q)|+max{|V(T),|V(R)|-|{y}|≤|V(H)|-min{|V(T)|, |V(R)|-|{y}|≤|V(H)|-d(H)-2, which contradicts the above inequality (*).

Thus, Claim holds.

Then we consider the following three cases.

Case 1. H is 2-connected.

let P*=x0x1¼xk be a path of length k in G. By |N(x)N(y)|≥n-d+k for any two vertices x,y in G with d(x,y)=2 and d£d(H)+|V(P*)|, where H=G-P*, we have inequality (*): |NH(x)NH(y)|≥n-d+k-|V(P*)|=(|V(H)|+|V(P*)|)-(d(H)+|V(P*)|)+k-|V(P*)|=|V(H)|-d(H)-1 for any two vertices x,y in H with dG(x,y)=2, where H=G-P*.

In this case, by Lemma 3, H has Hamiltonian path.

Subcase 1.1. If H has Hamiltonian cycle.

By |N(x)N(y)|≥n-d+k for any two vertices x,y in G with d(x,y)=2 and |N(x)N(y)|≤n-|{x,y}|=n-2, so d≥k+2. Thus, each of {x0,xk } must be adjacent to at least two vertices of H. Let P=y1y2¼yn-k-1 y1 be a Hamiltonian cycle of H and yi,yj are adjacent to x0,xk satisfying that none of {yi+1,yi+2¼,yj-1} are adjacent xk. By | NH(yi-1)NH(x0)|≥n-d-1 and | NH(yj-1)NH(xk)|≥n-d-1, we have the following. (i). When ytÎ(N(yi-1)N(x0)){yj,yj+1,¼,yi-1}, then yt-1 is not adjacent to yj-1 and xk ( Otherwise, if yt-1 is adjacent to yi-1, then path yiyi+1¼ yj-1yt+1yt+2¼yi-1ytyt-1¼ yj of H that its two end-vertices yi(=x0) and yj adjacent to x1,xk, respectively, a contradiction). (ii). When ytÎ( NH(yi-1)NH(x0)){yi,yi+1,¼,yj-1}\{ yi}, then yt+1 is not adjacent to yj-1 and xk. So we can check that |NH(yj-1)NH(xk)|(n-k-1)-| (NH(yi-1)NH(x0))\{yi}|-|{yj-1,xk}|(n-k-1)- (n-d-1)-1d-k, a contradiction.

Subcase 1.2. If H has not any Hamiltonian cycle.

In this case, we consider T=G-(P*\{xo}).

By |N(x)N(y)|≥n-d+k for any two vertices x,y in G with d(x,y)=2 and d£d(T)+|V(T)|, we have |NT(x)NT(y)|≥n-d+k-|V(P*\{xo})|=(|V(T)|+|V(P*)|)-(d(T)+|V(P*\{xo})|)+k-|V(P*\{xo})|=|V(T)|-d(T) for any two vertices x,y in T with dG(x,y)=2, where T=G-(P*\{xo}).

Since H=G-P* is 2-connected, and xo is adjacent to at least two vertices of H, so T=G-(P*\{xo}) is also 2-connected. By Lemma 3, T has Hamiltonian cycle, so we can complete the proof by the similar arguments as Subcase 1.1.

Case 2. the connectivity of H is 1.

In this case, by Lemma 4, H=Kh#K1#K(n-k-1)-h-1. Since x0,xk are at least adjacent to two vertices of H, so we consider the following.

(i). If x0,xk are adjacent to two vertices x,y with x in Kh and y in K(n-k-1)-h-1, then completing the proof.

(ii). If x0,xk are at most only adjacent to some vertices of Kh of K(n-k-1)-h-1. Without loss of generality, x0,xk are not adjacent to any vertex of K(n-k-1)-h-1, then x0,xk are all adjacent to every vertex of Kh.

Otherwise, if v of Kh is not adjacent to x0, then we can check that |NH(v)NH(xo)|≤|V(H)|-|{v}|-|V(K(n-k-1)-h-1}|≤|V(H)|-d(H)-2,, which contradicts inequality (*).

Similarly, if some vertex xi of P*\{ x0,xk } is adjacent to some vertex of Kh (or K(n-k-1)-h-1), then xi is adjacent to every vertex of Kh (or K(n-k-1)-h-1).

In this case, G is not k-path Hamiltonian and we denote graph G by (Kh#K1#K(n-k-1)-h-1)#G[P*], which x0,xk are at most all adjacent to every vertex of Kh or K(n-k-1)-h-1.

Case 3. H is not connected.

In this case, by the similar arguments to the Proof of Lemma 2, each component of G-P* must be complete subgraph. Then, we have the following claim.

Claim. G-P* has at most two component.

Otherwise, if G-P* has at least three components Q, R and T. We consider the following.

(i). If two of (Q, R, T) have common vertex in P*.

Without loss of generality, assume xi of P* is adjacent to vertex x in Q and y in R. Then similarly, we can check that | NH(x)NH(y)|≤|V(H)|-|V(T)|-|(x,y}|≤|V(H)|-d(H)-2, which contradicts inequality (*).

(ii). If any two of (Q, R, T) has not any common vertex in P*.

In this case, there must exist xi of P* is adjacent to vertex x in Q and xi +1 of P* is not adjacent to vertex x in Q. By (ii), xi +1 is not adjacent to any vertex of one {R, T}. Hence we can check that  | NH(x)NH(xi+1)|≤|V(Q)|+max{|V(R )|, |V(T)|}|-|{x}|≤|V(H)|-min{|V(R )|, |V(T)|}-|{x}|≤|V(H)|-d(H)-2, which contradicts inequality (*).

Thus, Chaim holds. In this case, G has not any Hamiltonian cycle containing path P*, and we denote G by G=(TQ)#G[P*], where T, Q are two complete subgraphs.

Therefore, the proof is complete.