Partial Degree Conditions and Cycle Coverings in Bipartite Graphs

Abstract

Let k be a positive integer. Let G be a graph of order $n\ge 3$ and W a subset of V(G) with $|W|\ge 3k$. Wang (J Graph Theory 78:295–304, 2015) proved that if $d(x)\ge 2n/3$ for each $x\in W$, then G contains k vertex-disjoint cycles such that each of them contains at least three vertices of W. In this paper, we obtain an analogue result of Wang’s Theorem in bipartite graph with the partial degree condition. Let $G=(V_1,V_2;E)$ be a bipartite graph with $|V_1|=|V_2|=n$, and let W be a subset of $V_1$ with $|W|\ge 2k$, where k is a positive integer. We show that if $d(x)+d(y)\ge n+k$ for every pair of nonadjacent vertices $x\in W, y\in V_2$, then G contains k vertex-disjoint cycles such that each of them contains at least two vertices of W.

1 Introduction

We discuss only finite simple graphs and use standard terminology and notation from [3] except as indicated. Let $G=(V(G),E(G))$ be a graph. We use E to denote the edge set of G if there is no confusion. For a subgraph H of G and a vertex $x\in V(G)$, N(x, H) stands for the set of neighbors of x in H and let $d(x,H)=|N(x,H)|$. The degree of x in G is briefly denoted by d(x). For a subset U of V(G), G[U] denotes the subgraph of G induced by U. For disjoint vertex-sets A and B, G[A, B] is the bipartite subgraph on A and B with all the edges of G between A and B. A set of graphs is said to be disjoint if no two of them have any vertex in common. The minimum degree of G is denoted by $\delta (G)$, and

$$\begin{aligned} \sigma _2(G)=\min \{d(x)+d(y)|x,y\in V(G), x\ne y, xy\notin E(G)\} \end{aligned}$$

is the minimum degree sum of nonadjacent vertices (When G is a complete graph, we define $\sigma _2(G)=\infty$). For a bipartite graph $G=(V_1,V_2; E)$, we define

$$\begin{aligned} \sigma _{1,1}(G)=\min \{d(x)+d(y)|x\in V_1, y\in V_2, xy\notin E(G)\}. \end{aligned}$$

When G is a complete bipartite graph, we define $\sigma _{1,1}(G)=\infty$.

In 1952, Dirac [7] obtained the following classical result on hamiltonian graphs using a minimum degree condition: if G is a graph of order $n\ge 3$ with $\delta (G)\ge n/2$, then G is hamiltonian. Ore [12] generalized the above result by using degree sum condition (Ore type condition) in 1960. He proved that if G is a graph of order $n\ge 3$ with $\sigma _2(G)\ge n$, then G is hamiltonian. Later, Moon and Moser [11] made the natural transition to bipartite graphs: if $G=(V_1,V_2; E)$ is a balanced bipartite graph of order 2n and $\sigma _{1,1}(G)\ge n+1$, then G is hamiltonian.

Let W be a subset of V(G), the set W is called cyclable in G if all vertices of W belong to a common cycle in G. Similarly, we define $\delta (W)$ to be the minimum degree of W in G and define

$$\begin{aligned} \sigma _2(W, G)=\min \{d(x)+d(y)|x,y\in W, x\ne y, xy\notin E(G)\} \end{aligned}$$

to be the minimum degree sum of nonadjacent vertices in W (When G[W] is a complete graph, we define $\sigma _2(W, G)=\infty$). For a bipartite graph $G=(V_1,V_2; E)$, let W be a subset of $V_1$, we define

$$\begin{aligned} \sigma _{1,1}(W, G)=\min \{d(x)+d(y)|x\in W, y\in V_2, xy\notin E(G)\}. \end{aligned}$$

When $G[W\cup V_2]$ is a complete bipartite graph, we define $\sigma _{1,1}(W, G)=\infty$.

Bollobás and Brightwell [2] considered partial degree condition for cyclable in graphs. They proved that if G is a graph on n vertices and W is a subset of V(G) with $|W|\ge 3$ and $\delta (W)\ge d$, then there is a cycle through at least $\lfloor \frac{|W|}{n/d-1}\rfloor$ vertices of W. When $d=n/2$, we have the following result, which is a generalization of Dirac’s [7] result.

Theorem 1.1

(Bollobás and Brightwell [2]) Let G be a graph of order n and W a subset of V(G) with $|W|\ge 3$. If $\delta (W)\ge n/2$, then W is cyclable.

Analogously, Shi [13] generalized Ore’s [12] result.

Theorem 1.2

(Shi [13]) Let G be a 2-connected graph of order n and W a subset of V(G) with $|W|\ge 3$. If $\sigma _2(W, G)\ge n$, then W is cyclable in G.

Later, Amar et al. [1] obtained a similar result for bipartite graphs:

Theorem 1.3

(Amar et al. [1]) Let $G=(V_1,V_2; E)$ be a 2-connected balanced bipartite graph of order 2n and W a subset of $V_1$. If $\sigma _{1,1}(W, G)\ge n+1$, then W is cyclable in G.

It is natural to ask that what is the degree condition and partial degree condition for disjoint cycles in graphs. In 1963, Corrádi and Hajnal [6] proved that every graph G with $|V(G)|\ge 3k$ and $\delta (G)\ge 2k$ contains k disjoint cycles. Later, Enomoto [8] and Wang [15] gave an Ore-type version, they proved that every graph G with $|V(G)|\ge 3k$ and $\sigma _2(G)\ge 4k-1$ contains k disjoint cycles. In 1996, Wang [14] considered the bipartite graph, he proved that every bipartite graph $G=(V_1, V_2; E)$ with $|V_1|=|V_2|=n > 2k$ and $\delta (G)\ge k+1$ contains k disjoint cycles. Recently, Wang [16] considered the partial degree condition for disjoint cycles.

Theorem 1.4

(Wang [16]) Let G be a graph of order $n\ge 3$. Let W be a subset of V(G) with $|W|\ge 3k$, where k is a positive integer. Suppose that $\delta (W)\ge 2n/3$. Then G contains k disjoint cycles such that each of the k cycles contains at least three vertices of W.

Naturally, can we consider the analogous problem on balanced bipartite graphs? We answer the question by proving the following theorem.

Theorem 1.5

Let $G=(V_1,V_2;E)$ be a bipartite graph with $|V_1|=|V_2|=n$, and let W be a subset of $V_1$ with $|W|\ge 2k$, where k is a positive integer. If $\sigma _{1,1}(W, G)\ge n+k$, then G contains k disjoint cycles such that each of them contains at least two vertices of W.

For other results on this topic, see [4, 5, 9, 10].

Remark 1

The following example shows that the degree condition in Theorem 1.5 is sharp when $k=1$. Let $G =(V_1,V_2;E)$ be a balanced bipartite graph with $V_1=\{u_1,\ldots , u_n\}$, $V_2=\{v_1,\ldots , v_n\}$ and $E=\{u_1v_1\}\cup \{u_iv_j|i,j\ge 2\}$, and suppose $u_1,u_2\in W$. Clearly, G does not contain a desired cycle and $\sigma _{1,1}(W, G)= n$. For $k>1$, the degree condition may be not sharp. But we can give an example to show that $\sigma _{1,1}(W, G)> n+\frac{\sqrt{16k+1}-1}{4}$ is necessary for the problem. Let $G=(V_1, V_2; E)$ be a balanced bipartite graph and let W be a subset of $V_1$ with the following properties:

• $|V_1|=|V_2|=n=2k+x$, $|W|=2k$, where k and x are positive integers and $2k-1$ is divisible by $x+1$.

• Let $W=W_0\cup W_1\cup \cdots \cup W_{x+1}$, $|W_0|=1$ and $|W_i|=\frac{2k-1}{x+1}$ for $1\le i\le x+1$.

• Let U be a subset of $V_2$, and $U=U_1\cup U_2\cup \cdots \cup U_{x+1}$, $|U_i|=1$ for $1\le i\le x+1$.

• Each of $G[W_0, U]$, $G[W_i, U_i]$, $G[V_1-W_0, V_2-U]$ is a complete bipartite subgraph of G, where $1\le i\le x+1$.

Clearly, $\sigma _{1,1}(W, G)=\min \{n+x, n-x+\frac{2k-1}{x+1}+1\}$. When $x=\frac{\sqrt{16k+1}-1}{4}$, we have $n+x = n-x+\frac{2k-1}{x+1}+1$, and so $\sigma _{1,1}(W, G)=n+\frac{\sqrt{16k+1}-1}{4}$. From the construction of G, we observe that any cycle containing the special vertex in $W_0$ must contain at least three vertices of W. Note that $|W|=2k$, G does not contain k disjoint cycles such that each of the k cycles contains at least two vertices of W.

We propose the following problem:

Problem 1.6

What is the best lower bound of $\sigma _{1,1}(W, G)$ to guarantee that G contains k disjoint cycles such that each of them contains at least two vertices of W?

Following [3], for a subgraph H of G, define $G-H=G[V(G)-V(H)]$. Let $G_1$ and $G_2$ be subgraphs of G. The union of $G_1$ and $G_2$, denoted by $G_1\cup G_2$, is the subgraph with vertex set $V(G_1)\cup V(G_2)$ and edge set $E(G_1)\cup E(G_2)$. We denote by $E[G_1,G_2]$ the set of edges of G with one end in $V(G_1)$ and the other end in $V(G_2)$, and by $e(G_1,G_2)$ their number. Clearly, $e(G_1,G_2)=\sum _{v\in G_i}d_{G_{3-i}}(v)$ for each $i=1,2$. If H is a subgraph of G, written as $G\supseteq H$.

We use the following notation in this paper. The length of a cycle C is denoted by l(C). If W is a subset of $V_1$, then the W-length of C is the number of vertices of C contained in W. We denote the W-length of C by $l_W(C)$. Similarly, for a path P, we define l(P) and $l_W(P)$ as above. If we write $C=x_1x_2\cdots x_mx_1$, we assume that an orientation of C is given such that $x_2$ is the successor of $x_1$ and operations in the subscripts of $x_i$’s will be taken modulo m in $\{1,2,\ldots , m\}$. Moreover, we use $x_i^+$ and $x_i^-$ to denote the successor and predecessor of $x_i$, respectively. We use $C[x_i,x_j]$ to represent the path of C from $x_i$ to $x_j$ along the orientation of C. We adopt the notation $C(x_i,x_j]=C[x_i,x_j]-x_i, C[x_i,x_j)=C[x_i,x_j]-x_j$ and $C(x_i,x_j)=C[x_i,x_j]-x_i-x_j$, respectively. Moreover, we define $\overleftarrow{C}[x_i,x_j]=x_jx_{j-1}\cdots x_i$. Similarly, we define $P[x_i,x_j], P(x_i,x_j], P[x_i,x_j), P(x_i,x_j)$ and $\overleftarrow{P}[x_i,x_j]$ as above.

The rest of the paper is organized as follows: we first present some useful lemmas in Sect. 2, and then prove the main theorem in Sect. 3.

2 Lemmas

In the following, $G=(V_1,V_2;E)$ is a balanced bipartite graph of order 2n and W is a subset of $V_1$.

Lemma 2.1

Let C be a cycle of W-length at least 2 and $l(C)\ge 6$. Let x and y be two distinct vertices of G not on C. Then the following three statements hold:

• (1) If $x\in W$ and $d(x,C)\ge 3$, then $G[V(C)\cup \{x\}]$ contains a cycle $C^\prime$ such that $l(C^\prime )<l(C)$ and $l_W(C^\prime )\ge 2$.

• (2) If $y\notin W$ and $d(y,C)\ge 5$, then $G[V(C)\cup \{y\}]$ contains a cycle $C^\prime$ such that $l(C^\prime )<l(C)$ and $l_W(C^\prime )\ge 2$.

• (3) If $x\in W, y\in V_2, xy\in E$ and $d(x,C)+d(y,C)\ge 5$, then $G[V(C)\cup \{x,y\}]$ contains a cycle $C^\prime$ such that $l(C^\prime )<l(C)$ and $l_W(C^\prime )\ge 2$.

Proof

Let $C=x_1y_1x_2y_2\cdots y_tx_1$ with $x_1\in V_1$ and $t=l(C)/2$. First, we prove (1). We may assume $\{y_{i_1},y_{i_2},y_{i_3}\}\subseteq N(x,C)$ with $1\le {i_1}< {i_2}< {i_3}\le t$. As $l_W(C)\ne 0$, it follows that $V(C[y_{i_j},y_{i_{j+1}}])\cap W\ne \emptyset$ for some $j\in \{1,2,3\}$, without loss of generality, we say $j=1$. Then the cycle $C^\prime =xC[y_{i_1}, y_{i_2}]x$ satisfies the requirement.

Next, we prove (2). We may assume $\{z_{i_1},z_{i_2},z_{i_3},z_{i_4},z_{i_5}\}\subseteq N(y,C)$ with $i_j<i_{j+1}$ for each $1\le j\le 4$, where $z_{i_j}=y_{i_j}$ if $y\in V_1$ and $z_{i_j}=x_{i_j}$ if $y\in V_2$. If $|V(C[z_{i_j},z_{i_{j+3}}])\cap W|\ge 2$ for some $j\in \{1,\ldots ,5\}$, then $C^\prime =yC[z_{i_j}, z_{i_{j+3}}]y$ satisfies the requirement. Hence we may assume $|V(C[z_{i_j},z_{i_{j+3}}])\cap W|\le 1$ for all $j\in \{1,\ldots ,5\}$. Since $l_W(C)\ge 2$ and $|V(C[z_{i_j},z_{i_{j+3}}]\cup C[z_{i_{j+3}},z_{i_{j+1}}])\cap W|\le 2$ for all $j\in \{1,\ldots ,5\}$, we have $V(C[z_{i_j},z_{i_{j+1}}])\cap W = \emptyset$ for all $j\in \{1,\ldots ,5\}$, it follows that $V(C)\cap W = \emptyset$, this is contrary to $l_W(C)\ge 2$.

Finally, we prove (3). By (1) and (2), we know if $d(x,C)\ge 3$ or $d(y,C)\ge 5$, we are done. So suppose that $d(x,C)\le 2$ and $d(y,C)\le 4$. Clearly, $1\le d(x,C)\le 2$ as $d(x,C)+d(y,C)\ge 5$. Now we show that $G[V(C)\cup \{x,y\}]$ contains a cycle $C^\prime$ satisfying the requirement. First we suppose that $d(x,C) = 1$. Thus $d(y,C) = 4$. We may assume $N(y,C) = \{x_{i_1},x_{i_2},x_{i_3},x_{i_4}\}$, where $i_j$ with ascending order, and $N(x,C) = \{y_j\}$ with $1\le j\le t$. Without loss of generality, we say $y_j\in V(C[x_{i_1},x_{i_2}])$. If $|V(C[y_j, x_{i_3}])\cap W|\ge 1$ or $|V(C[x_{i_4}, y_j])\cap W|\ge 1$, then $C^\prime =xC[y_j, x_{i_3}]yx$ or $C^\prime =yC[x_{i_4}, y_j]xy$. Otherwise, $|V(C[y_j, x_{i_3}])\cap W|=|V(C[x_{i_4}, y_j])\cap W|=0$, then $|V(C[x_{i_3}, x_{i_4}])\cap W|\ge 2$ as $l_W(C)\ge 2$, thus $C^\prime =yC[x_{i_3}, x_{i_4}]y$.

Then suppose $d(x,C) = 2$. Thus $d(y,C) \ge 3$. We may assume $N(y,C) \supseteq \{x_{i_1},x_{i_2},x_{i_3}\}$ with $1\le {i_1}< {i_2}< {i_3}\le t$ and $N(x,C) = \{y_{j_1},y_{j_2}\}$ with $1\le j_1 < j_2 \le t$. Without loss of generality, we say $y_{j_1}\in V(C[x_{i_1},x_{i_2}])$. First we show the case that $y_{j_2}\in V(C[x_{i_1},x_{i_2}])$. If $|V(C[y_{j_1}, x_{i_2}])\cap W|\ge 1$ or $|V(C[x_{i_3}, y_{j_1}])\cap W|\ge 1$, then $C^\prime =xC[y_{j_1}, x_{i_2}]yx$ or $C^\prime =yC[x_{i_3}, y_{j_1}]xy$. Otherwise, $|V(C[y_{j_1}, x_{i_2}])\cap W|=|V(C[x_{i_3}, y_{j_1}])\cap W|=0$, then $|V(C[x_{i_2}, x_{i_3}])\cap W|\ge 2$ as $l_W(C)\ge 2$, thus $C^\prime =yC[x_{i_2}, x_{i_3}]y$. Then we show the case that $y_{j_2}\notin V(C[x_{i_1},x_{i_2}])$, by symmetry, say $y_{j_2}\in V(C[x_{i_2},x_{i_3}])$. If one of $|V(C[x_{i_1}, y_{j_1}])\cap W|$, $|V(C[y_{j_1}, x_{i_2}])\cap W|$, $|V(C[x_{i_2}, y_{j_2}])\cap W|$ and $|V(C[y_{j_2}, x_{i_3}])\cap W|$ is at least 1, then one of the cycles $C^\prime =yC[x_{i_1}, y_{j_1}]xy$, $C^\prime =xC[y_{j_1}, x_{i_2}]yx$, $C^\prime =yC[x_{i_2}, y_{j_2}]xy$ and $C^\prime =xC[y_{j_2}, x_{i_3}]yx$ satisfies the requirement. Otherwise, $|V(C[x_{i_3}, x_{i_1}])\cap W|\ge 2$ as $l_W(C)\ge 2$, thus $C^\prime =yC[x_{i_3}, x_{i_1}]y$. $\square$

Lemma 2.2

[14] Let C be a quadrilateral and P a path of order 4 in G such that P is disjoint from C and $\sum _{x\in V(P)}d(x,C)\ge 6$. Then either $G[V(P\cup C)]$ contains two disjoint quadrilateral, or P has an endvertex, say z, such that $d(z,C)=0$.

Lemma 2.3

Let C be a cycle of W-length at least 2 with $l(C)\ge 4$. Let $x\in W$ and $y\in V_2$ be two distinct vertices of G not on C and $xy\notin E$. If $d(x,C)+d(y,C)\ge l(C)/2+2$, then $G[V(C)\cup \{x,y\}]$ contains a cycle $C^\prime$ such that $l(C^\prime )<l(C)$ and $l_W(C^\prime )\ge 2$ or $l(C)=4$ and $d(x,C)=d(y,C)=2$.

Proof

By Lemma 2.1 (1), (2), if $d(x,C)\ge 3$ or $d(y,C)\ge 5$, we are done. Thus $d(x,C)\le 2$ and $d(y,C)\le 4$. Note that $d(x,C)+d(y,C)\ge l(C)/2+2$, we have $l(C)\le 8$, i.e., $l(C)=4,6,8$. Clearly, $d(x,C)=d(y,C)=2$ if $l(C)=4$. Now we consider the case $l(C)\ne 4$. Note that $d(y,C)\ge l(C)/2+2-2=l(C)/2$. It is easy to see that $G[V(C)\cup \{y\}]$ contains a cycle $C^\prime$ such that $l(C^\prime )<l(C)$ and $l_W(C^\prime )\ge 2$. $\square$

Lemma 2.4

[14] Let t and s be two integers such that $t\ge s\ge 2$ and $t\ge 3$. Let $C_1$ and $C_2$ be two disjoint cycles of G with lengths 2t and 2s, respectively. Suppose that $\sum _{x\in V(C_1)}d(x,C_2)\ge 2t+1$. Then $G[V(C_1\cup C_2)]$ contains two disjoint cycles $C_1^\prime$ and $C_2^{\prime }$ such that $l(C_1^\prime )+l(C_2^{\prime })<2s+2t$.

Lemma 2.5

Let t and s be two integers such that $t\ge s\ge 2$ and $t\ge 3$. Let $C_1$ and $C_2$ be two disjoint cycles of G such that $l_W(C_1)=t, l_W(C_2)=s$. Suppose that $\sum _{x\in V(C_1)\cap W}(d(x,C_2)+d(x^+,C_2))\ge tl(C_2)/2+1$. Then $G[V(C_1\cup C_2)]$ contains two disjoint cycles $C_1^\prime$ and $C_2^{\prime }$ such that $l_W(C_1^\prime )\ge 2, l_W(C_2^{\prime })\ge 2$ and $l(C_1^\prime )+l(C_2^{\prime })<l(C_1)+l(C_2)$.

Proof

Suppose, for a contradiction, that the lemma fails. Let $s, t, G, W, C_1$ and $C_2$ be chosen with $l(C_1) + l(C_2)$ as small as possible such that the lemma fails for $C_1$ and $C_2$ while the conditions of the lemma are fulfilled. By Lemma 2.4, we see that $V(C_1\cup C_2)\cap V_1\nsubseteq W$. Thus $l(C_1) + l(C_2) > 2s + 2t$. First we claim that

$$\begin{aligned} l(C_1) = 2t. \end{aligned}$$

(1)

Proof of (1)

If this is not true, then there exists a vertex $x\in V_1\cap V(C_1)$ such that $x\notin W$. Clearly, $x^+, x^-\notin W$. Let $G^\prime =G-x-x^+ + x^-x^{++}, C_1^\prime =C_1-x-x^+ + x^-x^{++}$. Obviously, $l_W(C_1^\prime )=l_W(C_1)$ and $l(C_1^\prime )=l(C_1)-2$. And we also have $\sum _{x\in V(C_1^\prime )\cap W}(d(x,C_2)+d(x^+,C_2))\ge tl(C_2)/2+1$ in $G^\prime$. Thus by the minimality of $l(C_1) + l(C_2)$, the lemma holds for $C_1^\prime$ and $C_2$, that is, $G^\prime [V(C_1^\prime \cup C_2)]$ contains two disjoint cycles $Q^\prime$ and $Q^{\prime \prime }$ such that $l_W(Q^\prime )\ge 2, l_W(Q^{\prime \prime })\ge 2$ and $l(Q^\prime )+l(Q^{\prime \prime })<l(C_1^\prime )+l(C_2)$. If $x^-x^{++}\notin E(Q^\prime \cup Q^{\prime \prime })$, then $Q^\prime$ and $Q^{\prime \prime }$ are the two required cycles in $G[V(C_1 \cup C_2)]$. If $x^-x^{++}\in E(Q^\prime \cup Q^{\prime \prime })$, then we readily obtain the two required disjoint cycles of $G[V(C_1 \cup C_2)]$ from $Q^\prime$ and $Q^{\prime \prime }$ by replacing the edge $x^-x^{++}$ with the path $x^-xx^+x^{++}$, a contradiction. Hence $l(C_1) = 2t$. $\square$

Then we claim that the following (2) and (3) hold.

$$\begin{aligned}&\text{ For } \text{ each } v\in V(C_2)\cap V_1 \quad \text{ with } \nonumber \\&\quad |V(C_2)\cap W-v|\ge 2,\quad d(v,C_1)+d(v^+,C_1) > t. \end{aligned}$$

(2)

$$\begin{aligned}&\text{ For } \text{ each } v\in V(C_1)\cap V_1 \quad \text{ with } \quad |V(C_1)\cap W-v|\ge 3, \nonumber \\&\quad \text{ if } t-1\ge s,\quad d(v,C_2)+d(v^+,C_2) > l(C_2)/2. \end{aligned}$$

(3)

Proofs of (2) and (3)

We only need to show that for each $v\in V(C_i)\cap V_1$ with $|V(C_i)\cap W-v|\ge 4-i$, we have $d(v,C_{3-i})+d(v^+,C_{3-i}) > l(C_{3-i})/2$, where $i=1,2$. On the contrary, assume that $d(v,C_{3-i})+d(v^+,C_{3-i})\le l(C_{3-i})/2$ for some $v\in V(C_i)\cap V_1$ with $|V(C_i)\cap W-v|\ge 4-i$. Let $G^\prime =G-v-v^+ + v^-v^{++}, C_i^\prime =C_i-v-v^+ + v^-v^{++}$. Obviously, $l_W(C_i^\prime )\ge 4-i$ and $l(C_i^\prime )=l(C_i)-2$. If $i=2$, then $\sum _{x\in V(C_1)\cap W}(d(x,C_2^\prime )+d(x^+,C_2^\prime ))\ge tl(C_2)/2+1-t=tl(C_2^\prime )/2+1$ in $G^\prime$. If $i=1$, then $\sum _{x\in V(C_1^\prime )\cap W}(d(x,C_2)+d(x^+,C_2))\ge tl(C_2)/2+1-l(C_2)/2=(t-1)l(C_2)/2+1$ in $G^\prime$. Both of the above cases satisfy the condition of Lemma 2.5. By the minimality of $l(C_1) + l(C_2)$, the lemma holds for $C_i^\prime$ and $C_{3-i}$. By the similar argument of (1), (2) and (3) hold. $\square$

By (1) and $l(C_1) + l(C_2) > 2s + 2t$, we know $l(C_2) > 2s$. Let $C_1=x_1x_1^+\cdots x_tx_t^+x_1$ and $C_2=y_1y_1^+\cdots y_my_m^+y_1$ with $l(C_2)=2m$ and $x_1,y_1\in V_1$. Clearly, $m\ge 3$. We claim that

$$\begin{aligned} s=2. \end{aligned}$$

(4)

Proof of (4)

On the contrary, suppose $s\ge 3$. Thus for each $y\in V(C_2)\cap V_1$, we have $|V(C_2)\cap W-y|\ge 2$, so we see $d(y,C_1)+d(y^+,C_1) > t$ by (2). Note that $l(C_2) > 2s$, there exists a $y\in V(C_2)\cap V_1$ such that $y\notin W$. Let $G^\prime =G-y-y^+ + y^-y^{++}$, $C_2^\prime =C_2-y-y^+ + y^-y^{++}$. Obviously, $l_W(C_2^\prime )\ge 2$, $l(C_2^\prime )=l(C_2)-2$ and $\sum _{x\in V(C_1)}d(x,C_2^\prime )> tl(C_2^\prime )/2$ in $G^\prime$. By the minimality of $l(C_1) + l(C_2)$, the lemma holds for $C_1$ and $C_2^\prime$. By the similar argument of (1), the Eq. (4) holds. $\square$

$$\begin{aligned} t=3. \end{aligned}$$

(5)

Proof of (5)

On the contrary, suppose $t\ge 4$. Thus for each $x\in V(C_1)\cap V_1$, we have $|V(C_1)\cap W-x|\ge 3$ and $t-1\ge 3\ge s$, so we see $d(x,C_2)+d(x^+,C_2) > l(C_2)/2$ by (3). For some vertex $x\in V(C_1)\cap V_1$, let $G^\prime =G-x-x^+ + x^-x^{++}, C_1^\prime =C_1-x-x^+ + x^-x^{++}$. Obviously, $l_W(C_1^\prime )=t-1\ge 3$ and $l(C_1^\prime )=l(C_1)-2$. And we also have $\sum _{x\in V(C_1^\prime )\cap W}(d(x,C_2)+d(x^+,C_2))> (t-1)l(C_2)/2$ in $G^\prime$. Thus by the minimality of $l(C_1) + l(C_2)$, the lemma holds for $C_1^\prime$ and $C_2$. By the similar argument of (1), the Eq. (5) holds. $\square$

$$\begin{aligned}&\text{ For } \text{ each } y\in V_1\cap V(C_2),\quad \text{ if } y\notin W,\nonumber \\&\quad \text{ then } d(y^+,C_1)+|N(y,C_1)\cap N(y^{++},C_1)|\ge 4. \end{aligned}$$

(6)

Proof of (6)

On the contrary, suppose that $d(y^+,C_1)+|N(y,C_1)\cap N(y^{++},C_1)|\le 3$ for some $y \in V_1\cap V(C_2)$ and $y\notin W$. We identify $y, y^+$ and $y^{++}$ as a new vertex $y_0$, obtaining a new graph $G^\prime$ where the neighborhood of $y_0$ contains all the neighbors of y and $y^{++}$ except $y^+$. Then $C_2$ becomes a new cycle $C_2^\prime =C_2-y-y^+-y^{++}+y_0+y_0y^-+y_0y^{+++}$ with $l(C_2^\prime )=l(C_2)-2$ and $l_W(C_2)=l_W(C_2^\prime )$ ($y_0\in W$ if $y^{++}\in W$, otherwise $y_0\notin W$). Note that $\sum _{x\in V(C_1)}d(x,C_2)\ge tl(C_2)/2+1$. By (5) and $d(y^+,C_1)+|N(y,C_1)\cap N(y^{++},C_1)|\le 3$, we obtain $\sum _{x\in V(C_1)}d(x,C_2^\prime )\ge 3l(C_2)/2+1-3=3l(C_2^\prime )/2+1$ in $G^\prime$. Thus by the minimality of $l(C_1) + l(C_2)$, the lemma holds for $C_1$ and $C_2^\prime$, that is, $G^\prime [V(C_1 \cup C_2^\prime )]$ contains two disjoint cycles $Q^\prime$ and $Q^{\prime \prime }$ such that $l_W(Q^\prime )\ge 2, l_W(Q^{\prime \prime })\ge 2$ and $l(Q^\prime )+l(Q^{\prime \prime })<l(C_1)+l(C_2^\prime )$. If $y_0\notin V(Q^\prime \cup Q^{\prime \prime })$, then $Q^\prime$ and $Q^{\prime \prime }$ are the two required cycles. Then we may assume that $y_0\in V(Q^\prime \cup Q^{\prime \prime })$. By symmetry, say $y_0\in V(Q^\prime )$. Let $uy_0v$ be a path of $Q^\prime$. If $\{u,v\}\subseteq N(y^\prime ,Q^\prime )$ for some $y^\prime \in \{y,y^{++}\}$, then we readily obtain the two required disjoint cycles of $G[V(C_1 \cup C_2)]$ from $Q^\prime$ and $Q^{\prime \prime }$ by replacing the vertex $y_0$ with $y^\prime$, a contradiction. Otherwise, we readily obtain the two required disjoint cycles of $G[V(C_1 \cup C_2)]$ from $Q^\prime$ and $Q^{\prime \prime }$ by replacing the vertex $y_0$ with the path $yy^+y^{++}$, a contradiction. $\square$

By the similar argument of (6) (identify $y^-, y^+$ and y as a new vertex $y_0$, obtaining a new graph $G^\prime$ where the neighborhood of $y_0$ contains all the neighbors of $y^-$ and $y^+$ except y), we have the following statement:

$$\begin{aligned}&\text{ for } \text{ each } y\in V_1\cap V(C_2),\quad \text{ if } y\notin W,\nonumber \\&\quad \text{ then } d(y,C_1)+|N(y^-,C_1)\cap N(y^{+},C_1)|\ge 4. \end{aligned}$$

(7)

By (5), $C_1=x_1x_1^+x_2x_2^+x_3x_3^+x_1$. Note that $C_2=y_1y_1^+\cdots y_my_m^+y_1$, where $m\ge 3$. By (4), there exists a vertex $y\in V_1\cap V(C_2)$ such that $y\notin W$. Choose y such that $|\{y,y^{++}\}\cap W|$ is minimum. We may assume $y=y_1$. According to (6) and (7), we find $d(y_1^+,C_1)+|N(y_1,C_1)\cap N(y_2,C_1)|\ge 4$ and $d(y_1,C_1)+|N(y_m^+,C_1)\cap N(y_1^+,C_1)|\ge 4$. Clearly, $d(y_1^+,C_1)\ge 1$.

If $d(y_1^+,C_1)=3$, then $|N(y_1,C_1)\cap N(y_2,C_1)|\ge 1$. Assume $y_1x_3^+, y_2x_3^+\in E$. Also, if $d(y_1^+,C_1)=2$, then $|N(y_1,C_1)\cap N(y_2,C_1)|\ge 2$. Assume $y_1^+x_2, y_1^+x_3\in E$. Obviously, $|N(y_1,C_1)\cap N(y_2,C_1)-x_2^+|\ge 1$, by symmetry, we may assume $y_1x_3^+, y_2x_3^+\in E$. Then in both cases $G[V(C_1 \cup C_2)]$ contains two required disjoint cycles $C_1^\prime$ and $C_2^\prime$ with $C_1^\prime =y_1^+x_2x_2^+x_3y_1^+$ and $C_2^\prime =y_1x_3^+C_2[y_2,y_m^+]y_1$, where $l(C_1^\prime )=4$ and $l(C_2^\prime )=2m$, a contradiction. Thus $d(y_1^+,C_1)=1$ and $d(y_1,C_1)=d(y_2,C_1)=3$, say $y_1^+x_3\in E$. Since $d(y_1,C_1)+|N(y_m^+,C_1)\cap N(y_1^+,C_1)|\ge 4$, we have $|N(y_m^+,C_1)\cap N(y_1^+,C_1)|\ge 1$. Then $y_m^+x_3\in E$.

If $y_2\notin W$, then $y_1^+,y_2, y_2^{+}$ satisfy (7), thus we have $|N(y_1^+,C_1)\cap N(y_2^{+},C_1)|\ge 1$, hence $y_2^{+}x_3\in E$. It follows that $G[V(C_1 \cup C_2)]$ contains two required disjoint cycles $C_1^\prime$ and $C_2^\prime$ with $C_1^\prime =y_1x_2^+x_2x_1^+x_1x_3^+y_1$ and $C_2^\prime =x_3C_2[y_2^{+},y_m^+]x_3$, where $l(C_1^\prime )=6$ and $l(C_2^\prime )=2m-2$, a contradiction. Thus $y_2\in W$. By the choice of y, we find $y_m\in W$.

First suppose $m\ge 4$. Then $y_{m-1}\notin W$, and thus $y_{m-1},y_{m-1}^+, y_m$ satisfy (6). Clearly, $d(y_{m-1}^+,C_1)\ge 1$. Since $x_1$ and $x_2$ are symmetric, we only need to consider the case $y_{m-1}^+x_2\in E$ or $y_{m-1}^+x_3\in E$. Let $C_1^\prime =y_2x_1^+x_1x_3^+y_2$. Then $C_2^\prime =y_{m-1}^+x_2x_2^+x_3y_m^+y_my_{m-1}^+$ or $C_2^\prime =y_{m-1}^+x_3y_m^+y_my_{m-1}^+$. Clearly, $l_W(C_1^\prime )\ge 2, l_W(C_2^\prime )\ge 2$ and $l(C_1^\prime )+l(C_2^\prime )<l(C_1)+l(C_2)$, a contradiction.

Then suppose $m=3$. Since $\sum _{x\in V(C_1)}d(x,C_2)\ge tl(C_2)/2+1=10$, $d(y_1^+,C_1)=1$, and $d(y_1,C_1)=d(y_2,C_1)=3$, we have $d(y_3,C_1)+d(y_3^+,C_1)+d(y_2^+,C_1)\ge 3$. If $d(y_k^+,C_1)\ge 2$ for some $k\in \{2,3\}$, as $x_1=x_{3+1}$, we say $\{x_i,x_{i+1}\}\subseteq N(y_k^+,C_1)$. This implies that $G[V(C_1)\cup \{y_2,y_k^+\}]$ contains two disjoint cycles $C_1^\prime$ and $C_2^\prime$ such that $C_1^\prime =y_k^+x_ix_i^+x_{i+1}y_k^+$ and $C_2^\prime =y_2x_{i+1}^+x_{i+2}x_{i+2}^+y_2$, where $l_W(C_1^\prime )\ge 2, l_W(C_2^\prime )\ge 2$, a contradiction. Thus $d(y_k^+,C_1)\le 1$ for all $k\in \{2,3\}$, so we have $d(y_3,C_1)\ge 1$. Say $y_3x_i^+\in E$ for some $i\in \{1,2,3\}$. If $i\in \{2,3\}$, then $G[V(C_1\cup C_2)]$ contains two disjoint cycles $y_3x_i^+x_3y_3^+y_3$ and $y_2x_{i+1}^+x_{i+2}x_{i+2}^+y_2$, again a contradiction. Thus $i=1$, and $d(y_k^+,C_1)=1$ for all $k\in \{2,3\}$. Then $y_2^+x_j\in E$ for some $j\in \{1,2,3\}$. It follows that $G[V(C_1\cup C_2)]$ contains two disjoint cycles $y_3x_1^+x_jy_2^+y_3$ and $y_2x_2^+x_3x_3^+y_2$ if $j\in \{1,2\}$ and $G[V(C_1\cup C_2)]$ contains two disjoint cycles $y_3y_3^+x_3y_2^+y_3$ and $y_2x_1^+x_2x_2^+y_2$ if $j=3$, a contradiction. $\square$

3 Proof of Theorem 1.5

Let $G=(V_1,V_2;E)$ be a bipartite graph with $|V_1|=|V_2|=n$, and let W be a subset of $V_1$ with $|W|\ge 2k$, and $d(x)+d(y)\ge n+k$ for all $x\in W, y\in V_2$ with $xy\notin E$, where k is a positive integer. Suppose, for a contradiction, that G does not contain k disjoint cycles of W-length at least 2. We may assume that $G+xy$ contains k disjoint cycles of W-length at least 2 for each pair of nonadjacent vertices $x\in V_1$ and $y\in V_2$ of G. Thus G contains $k-1$ disjoint cycles $C_1, \ldots , C_{k-1}$ of W-length at least 2. We choose such a set of cycles $C_1, \ldots , C_{k-1}$ that

$$\begin{aligned} \sum _{i=1}^{k-1}l(C_i) \text{ is } \text{ minimum. } \end{aligned}$$

(8)

Subject to (8), we choose $C_1, \ldots , C_{k-1}$ such that

$$\begin{aligned} \sum _{i=1}^{k-1}l_W(C_i) \text{ is } \text{ minimum. } \end{aligned}$$

(9)

Subject to (8) and (9), we choose $C_1, \ldots , C_{k-1}$ and a path P in $G-V(\bigcup _{i=1}^{k-1}C_i)$ such that

$$\begin{aligned} |V(P)\cap W| \text{ is } \text{ maximum. } \end{aligned}$$

(10)

Subject to (8), (9) and (10), we finally choose $C_1, \ldots , C_{k-1}$ and P such that

$$\begin{aligned} l(P) \text{ is } \text{ minimum. } \end{aligned}$$

(11)

Set $H=\bigcup _{i=1}^{k-1}C_i$, $D=G-V(H)$, $W_0=W\cap V(D)$ and $|V(D)|=2d$. Let $D_0=D-V(P)$ and $P=x_1x_2\dots x_{2p+1}$. By (11), $\{x_1,x_{2p+1}\}\subseteq W_0$.

Claim 3.1

$l_W(C_i)=2$ for all $i\in \{1,2,\ldots k-1\}$.

Proof

On the contrary, suppose that Claim 3.1 fails. We may assume $l_W(C_1)\ge l_W(C_i)$ for all $i\in \{1,2,\ldots , k-1\}$. Then $l_W(C_1)\ge 3$. Set $t=l_W(C_1)$. We may assume $V(C_1)\cap W=\{u_{i_1}, u_{i_2}, \ldots ,u_{i_{t}}\}$, where $i_j<i_{j+1}$ for each $1\le j\le t-1$. Let $L_1=\{u_{i_1}, u_{i_2}, \ldots ,u_{i_t}\}$ and $L_2=\{u_{i_1}^+, u_{i_2}^+, \ldots ,u_{i_t}^+\}$. First we claim that

$$\begin{aligned} N(u_{i_j},D)\cap N(u_{i_k},D)= & {} \emptyset \quad \text{ for } \text{ each }\quad j\ne k. \end{aligned}$$

(12)

$$\begin{aligned} N(u_{i_j}^+,D)\cap N(u_{i_k}^+,D)= & {} \emptyset \quad \text{ for } \text{ each }\quad j\ne k. \end{aligned}$$

(13)

In fact, if there exists a pair j, k such that $N(u_{i_j},D)\cap N(u_{i_k},D)\ne \emptyset$, we may assume $u_{i_j}u, u_{i_k}u\in E$, where $u\in V(D)$, then we replace $C_1$ with $C_1^\prime =uC_1[u_{i_p}, u_{i_q}]u$ if $|C_1[u_{i_p}, u_{i_q}]|\le |C_1[u_{i_q}, u_{i_p}]|$ with $\{p,q\}=\{j,k\}$, where $l(C_1^\prime )< l(C_1)$, this is contrary to (8). And if there exists a pair j, k such that $N(u_{i_j}^+,D)\cap N(u_{i_k}^+,D)\ne \emptyset$, we may assume $u_{i_j}^+u, u_{i_k}^+u\in E$. If $u\in W_0$, then we replace $C_1$ with $C_1^\prime =uC_1[u_{i_p}^+,u_{i_q}^+]u$ if $|C_1[u_{i_p}^+, u_{i_q}^+]|\le |C_1[u_{i_q}^+, u_{i_p}^+]|$ with $\{p,q\}=\{j,k\}$, where $l(C_1^\prime )< l(C_1)$, contradicting (8). If $u\notin W_0$, then we replace $C_1$ with $C_1^\prime = uC_1[u_{i_q}^+, u_{i_p}^+]u$ if $l_W(C_1[u_{i_p}^+, u_{i_q}^+])\le l_W(C_1[u_{i_q}^+, u_{i_p}^+])$ with $\{p,q\}=\{j,k\}$, where $l(C_1^\prime )\le l(C_1)$ and $2\le l_W(C_1^\prime )<l_W(C_1)$ as $l_W(C_1)\ge 3$, contradicting (8) or (9).

Thus we have $\sum _{u\in L_1}d(u,D)\le d$ and $\sum _{u\in L_2}d(u,D)\le d$ according to (12) and (13). By (8), it is easy to see that $d(u_{i_{a}},G[V(C_1)])=d(u_{i_{a}}^+,G[V(C_1)])=2$ and $u_{i_{a}}u_{i_{a+1}}^+\notin E$ for each $1\le a\le t$. So we have $\sum _{u\in L_1+L_2}d(u,G[V(D\cup C_1)])\le 2d+4t$ and $\sum _{u\in L_1+L_2}d(u)\ge t(n+k)$. Then we have $\sum _{u\in L_1+L_2}d(u,H-C_1)\ge t(n+k)-2d-4t\ge t\sum _{i=2}^{k-1}l(C_i)/2+t(k-1)+(t-2)d\ge t\sum _{i=2}^{k-1}l(C_i)/2+1$ as $l(C_1)\ge 6$ and $t\ge 3$. This implies that there exists a cycle $C_i\in H-C_1$, say $C_2$, such that $\sum _{u\in L_1+L_2}d(u,C_2)\ge tl(C_2)/2+1$. By Lemma 2.5, $G[V(C_1\cup C_2)]$ contains two disjoint cycles $C_1^\prime$ and $C_2^{\prime }$ such that $l_W(C_1^\prime )\ge 2, l_W(C_2^{\prime })\ge 2$ and $l(C_1^\prime )+l(C_2^{\prime })<l(C_1)+l(C_2)$, contradicting (8). $\square$

By Claim 3.1, we observe that $|V(P)|\ge 1$. If $|V(P)|=1$, we say $P=x_{2p+1}$.

Claim 3.2

$d(x_{2p+1},P)\le 1$, and if $x_1$ exists, then $d(x_1,P)\le 1$.

Proof

On the contrary, suppose $d(x_{2p+1},P)\ge 2$, we may assume $\{x_{2i}, x_{2p}\}\subseteq N(x_{2p+1},P)$. Note that D does not contain a cycle with W-length at least two, $l_W(P[x_{2i}, x_{2p}])=0$. We obtain a short path by replacing P with $P^\prime =P[x_1,x_{2i}]x_{2p+1}$, this contradicts (11) while (8)–(10) hold. By symmetry, it is easy to see if $x_1$ exists, then $d(x_1,P)\le 1$. $\square$

Claim 3.3

We can choose $D_0$ such that $d(x_{2p+1},D_0)\ne 0$, and if $|D_0|\ge 2$ and $x_1$ exists, then $d(x_1,D_0)\ne 0$.

Proof

Suppose that $d(x_{2p+1},D_0)= 0$, then there exists a $y\in V_2\cap D_0$ such that $x_{2p+1}y\notin E$. By Claim 3.2, $d(x_{2p+1},P)\le 1$. Thus $d(x_{2p+1},D)+d(y,D)\le 1+d-1=d$. Since $x_{2p+1}y\notin E$ and $x_{2p+1}\in W$, we have $d(x_{2p+1},H)+d(y,H)\ge n+k-d=\sum _{i=1}^{k-1}l(C_i)/2+(k-1)+1$. This implies that there exists a cycle $C_i\in H$, say $C_1$, such that $d(x_{2p+1},C_1)+d(y,C_1)\ge l(C_1)/2+2$. By Lemma 2.3 and (8), we have $l(C_1)=4$ and $d(x_{2p+1},C_1)=d(y,C_1)=2$. Let $C_1=u_1u_2u_3u_4u_1$ with $u_1\in V_1$. Then we find a $D_0$ such that $d(x_{2p+1},D_0)\ne 0$ by replacing $C_1$ and $D_0$ with $C_1^\prime =yu_1u_2u_3y$ and $D_0^\prime =D_0-y+u_4$. We may assume $x_{2p+1}y\in E$. If $|V(D_0)|\ge 2$, then $|V(D_0)-y|\ge 1$. By a similar argument( replacing $x_{2p+1}$ with $x_1$), we can find a $D_0$ such that $d(x_1,D_0-y)\ne 0$ and $d(x_{2p+1},D_0)\ne 0$. $\square$

Let $D_0$ be chosen satisfying Claim 3.3, so there exists a vertex in $D_0\cap V_2$, say y, such that

$$\begin{aligned} x_{2p+1}y\in E. \end{aligned}$$

(14)

Claim 3.4

$V(P)\supseteq W_0.$

Proof

On the contrary, suppose $V(P)\nsupseteq W_0$. Let $x_0\in W_0\cap V(D_0)$. According to (10) and (14), $x_0y\notin E$. First we claim that $d(x_0,P)+d(y,P)\le p+1$. Otherwise, $d(x_0,P)+d(y,P)\ge p+2$, i.e., $d(x_0,P-x_{2p+1})+d(y,P-x_{2p+1})\ge p+1$, then $x_{2i-1}y,x_{2i}x_0\in E$ for some $1\le i\le p$. Let $P^\prime =P[x_1,x_{2i-1}]y\overleftarrow{P}[x_{2i}, x_{2p+1}]x_0$. Obviously, $l_W(P^\prime )>l_W(P)$, this is contrary to (10).

We divide the proof of the claim into two cases.

Case 1. $d(x_0,D_0-y)=0$.

By the claim above, we have $d(x_0,P)+d(y,P)\le p+1$. Thus $d(x_0,D)+d(y,D)\le p+1+d-p-2=d-1$ as $x_0y\notin E$. Since $x_0y\notin E$ and $x_0\in W$, we have $d(x_0,H)+d(y,H)\ge n+k-(d-1)=\sum _{i=1}^{k-1}l(C_i)/2+k+1$. This implies that there exists a cycle $C_i\in H$, say $C_1$, such that $d(x_0,C_1)+d(y,C_1)\ge l(C_1)/2+2$. By Lemma 2.3 and (8), we have $l(C_1)=4$ and $d(x_0,C_1)=d(y,C_1)=2$. Let $C_1=u_1u_2u_3u_4u_1$ with $u_1\in V_1$. We replace $C_1$ and P with $C_1^\prime =x_0u_2u_3u_4x_0$ and $P^\prime =Pyu_1$, then $l_W(P^\prime )>l_W(P)$, this contradicts (10) while (8)–(9) hold.

Case 2. $d(x_0,D_0-y)\ne 0$, i.e., there exists a vertex $y_0\in V(D_0-y)\cap V_2$ such that $x_0y_0\in E$.

By (10), we see $N(x_{2p+1},D_0)\cap N(x_0,D_0)=\emptyset , N(y,D_0)\cap N(y_0,D_0)=\emptyset$. In particular, we have $x_{2p+1}y_0,x_0y\notin E$. Set $L=\{x_{2p+1}, y, x_0, y_0\}$. Thus we have $\sum _{x\in L}d(x,D_0)\le d-p+d-p-1=2d-2p-1$ and $\sum _{x\in L}d(x)\ge 2(n+k)$. Recall that $d(x_0,P)+d(y,P)\le p+1$, and $d(x_{2p+1},P)\le 1$ by Claim 3.2, we have $\sum _{x\in L}d(x,D)\le 2d-2p-1+1+p+p+1=2d+1$. Thus $\sum _{x\in L}d(x,H)\ge 2(n+k)-2d-1=\sum _{i=1}^{k-1}l(C_i)+2(k-1)+1$. This implies that there exists a cycle $C_i\in H$, say $C_1$, such that $\sum _{x\in L}d(x,C_1)\ge l(C_1)+3$. Then $d(x_{2p+1},C_1)+d(y_0,C_1)\ge l(C_1)/2+2$ or $d(x_0,C_1)+d(y,C_1)\ge l(C_1)/2+2$. By Lemma 2.3 and (8), we have $l(C_1)=4$. Thus $\sum _{x\in L}d(x,C_1)\ge 7$. It follows that $d(x_{2p+1},C_1)+d(x_0,C_1)\ge 3$ and $d(y^\prime ,C_1)=2$ for some $y^\prime \in \{y,y_0\}$. Let $C_1=u_1u_2u_3u_4u_1$ with $u_1\in V_1$. We may assume $x_{2p+1}u_4,x_0u_4\in E$ as $d(x_{2p+1},C_1)+d(x_0,C_1)\ge 3$. Then $G[V(P\cup C_1)\cup \{y,x_0,y_0\}]$ contains a cycle $C_1^\prime$ and a path $P^\prime$ such that $C_1^\prime =y^\prime u_1u_2u_3y^\prime$ and $P^\prime =Pu_4x_0$, where $l_W(P^\prime )>l_W(P)$, a contradiction. $\square$

Claim 3.5

$|W_0|\le 2$.

Proof

On the contrary, suppose $|W_0|\ge 3$. Say $\{x_1,x_{2a+1},x_{2p+1}\}\subseteq W_0$, where $1<a<p$ and $V(P(x_{2a+1},x_{2p+1}))\cap W=\emptyset$. By our assumption, we know D does not contain a cycle of W-length at least 2, thus we have $d(y, P[x_1,x_{2a+1}])=0$ as $x_{2p+1}y\in E$, and $|N(x_{2p+1},D_0)\cap N(x_{2a+1},D_0)|=|N(y,D_0)\cap N(x_{2a},D_0)|=0$. In particular, $x_{2a+1}y, x_{2p+1}x_{2a}\notin E$. According to (11) and Claim 3.2, we have $d(x_{2a+1},P(x_{2a+2},x_{2p}])=0$ and $d(x_{2p+1},P)\le 1$. Set $L=\{x_{2p+1}, y, x_{2a+1}, x_{2a}\}$. We see $\sum _{x\in L}d(x,D)\le d-p+d-p-1+1+p-a+a+1+p=2d+1$. Hence $\sum _{x\in L}d(x,H)\ge 2(n+k)-2d-1=\sum _{i=1}^{k-1}l(C_i)+2(k-1)+1$. This implies that there exists a cycle $C_i\in H$, say $C_1$, such that $\sum _{x\in L}d(x,C_1)\ge l(C_1)+3$. On the other hand, by Lemma 2.1 (3) and (8), we obtain $\sum _{x\in L}d(x,C_1)\le 4+4=8$. Then $l(C_1)+3\le 8$, i.e., $l(C_1)=4$. Let $C_1=u_1u_2u_3u_4u_1$ with $u_1\in V_1$. Thus $\sum _{x\in L}d(x,C_1)\ge 7$. It follows that $d(x_{2p+1},C_1)+d(x_{2a+1},C_1)\ge 3$ and $d(y^\prime ,C_1)=2$ for some $y^\prime \in \{y,x_{2a}\}$. We may assume $x_{2p+1}u_2,x_{2a+1}u_2\in E$. It follows that $G[V(P\cup C_1)\cup \{y\}]$ contains two disjoint cycles $C_1^\prime$ and $C^\prime$ such that $C_1^\prime =y^\prime u_1u_4u_3y^\prime$ and $C^\prime =u_2P[x_{2a+1},x_{2p+1}]u_2$, where $l_W(C^\prime )\ge 2$, a contradiction. $\square$

By Claims 3.1, 3.5 and $|W|\ge 2k$, we have $|W|=2k$ and $|W_0|=2$. Then $W_0=\{x_1,x_{2p+1}\}$. By our assumption and (14), $x_1y\notin E$. By Claim 3.3, we know if $|D_0|\ge 2$, then $d(x_1,D_0)\ne 0$. We divide the proof of the theorem into two cases.

Case 1. $|D_0|\ge 2$, then there exists a $y_1\in V(D_0-y)\cap V_2$, such that $x_1y_1\in E$.

By our assumption, we know D does not contain a cycle C such that $l_W(C)\ge 2$. Then we have $d(y,D_0)+d(y_1,D_0)\le d-p-1$, $d(x_1,D_0)+d(x_{2p+1},D_0)\le d-p$ and $x_1y,x_{2p+1}y_1\notin E$. Thus, we also have $d(y,P)\le p, d(y_1,P)\le p$. Set $L=\{x_1,y_1,x_{2p+1},y\}$. Then $\sum _{x\in L}d(x,D_0)\le 2d-2p-1$. By Claim 3.2, we have $d(x_1,P)=d(x_{2p+1},P)=1$. Then $\sum _{x\in L}d(x,D)\le 2d-2p-1+2p+2=2d+1$. Thus $\sum _{x\in L}d(x,H)\ge 2(n+k)-2d-1=\sum _{i=1}^{k-1}l(C_i)+2(k-1)+1$. This implies that there exists a cycle $C_i\in H$, say $C_1$, such that $\sum _{x\in L}d(x,C_1)\ge l(C_1)+3$. On the other hand, by Lemma 2.1 (3) and (8), we obtain $\sum _{x\in L}d(x,C_1)\le 4+4=8$. Then $l(C_1)+3\le 8$, i.e., $l(C_1)=4$. Then $\sum _{x\in L}d(x,C_1)\ge 7$. Let $C_1=u_1u_2u_3u_4u_1$ with $u_1\in V_1$. Clearly, $d(y^\prime ,C_1)=2$ for some $y^\prime \in \{y,y_1\}$ and $d(x_{2p+1},C_1)+d(x_1,C_1)\ge 3$, say $x_{2p+1}u_2,x_1u_2\in E$. It follows that $G[V(P\cup C_1)\cup \{y,y_1\}]$ contains two disjoint cycles $C_1^\prime$ and $C^\prime$ such that $C_1^\prime =y^\prime u_1u_4u_3y^\prime$ and $C^\prime =u_2P[x_1,x_{2p+1}]u_2$, where $l_W(C^\prime )\ge 2$, a contradiction.

Case 2. $|D_0|=1$, thus $|D|=2p+2$.

According to $x_1y\notin E$ and Claim 3.2, we have $d(x_1,D)=1$ and $d(y,D)\le p$. Thus $d(x_1,H)+d(y,H)\ge n+k-p-1=\sum _{i=1}^{k-1}l(C_i)/2+(k-1)+1$. This implies that there exists a cycle $C_i\in H$, say $C_1$, such that $d(x_1,C_1)+d(y,C_1)\ge l(C_1)/2+2$. By Lemma 2.3 and (8), we have $l(C_1)=4$ and $d(x_1,C_1)=d(y,C_1)=2$. Let $C_1=u_1u_2u_3u_4u_1$ with $u_1\in V_1$. We replace $C_1$ and P with $C_1^\prime =x_1u_2u_3u_4x_1$ and $P^\prime =x_{2p+1}yu_1$, then by (11) we have $|P|=3$. So we have that $D=x_1x_2x_3y$ be a 4-path.

By our assumption, $G[V(D\cup C_1)]$ does not contain two disjoint cycles $C^\prime$ and $C^{\prime \prime }$ such that $l_W(C^\prime )\ge 2, l_W(C^{\prime \prime })\ge 2$. Thus we see $d(x_2,C_1)=d(x_3,C_1)=0$. So we have $x_3u_2,x_2u_1\notin E$. Set $L=\{x_1,x_2,x_3,y,u_1,u_2\}$. It is easy to see that $\sum _{x\in L}d(x, D+ C_1)=3+2+2+3+3+3=16$. Recall that $x_1y,x_3u_2,x_2u_1\notin E$, we have $\sum _{x\in L}d(x, H- C_1)\ge 3(n+k)-16=3\sum _{i=2}^{k-1}l(C_i)/2+3(k-2)+2$. This implies that there exists a cycle $C_i\in H-C_1$, say $C_2$, such that $\sum _{x\in L}d(x,C_2)\ge 3l(C_2)/2+4$. On the other hand, we see $G[V(D\cup C_1)-\{p,q\}]$ contains a cycle of W-length at least two with $\{p, q\}\in \{\{x_1, u_2\}, \{x_2, x_3\}, \{u_1, y\}\}$, then by Lemma 2.1 (3), (8) and $x_1u_2, x_2x_3, u_1y\in E$, we obtain $\sum _{x\in L}d(x,C_2)\le 4+4+4=12$. Then $3l(C_2)/2+4\le 12$, i.e., $l(C_2)=4$. Thus $\sum _{x\in L}d(x,C_2)\ge 10$. Let $C_2=v_1v_2v_3v_4v_1$ with $v_1\in V_1$. By our assumption and by Lemma 2.2, $\sum _{x\in D}d(x,C_2)\le 6$ and if $\sum _{x\in D}d(x,C_2)=6$, then $d(x_1,C_2)=0$ or $d(y,C_2)=0$. Recall that $\sum _{x\in L}d(x,C_2)\ge 10$, we see $d(u_1,C_2)=d(u_2,C_2)=2$ and $d(x_1,C_2)=0$ or $d(y,C_2)=0$. It follows that $G[V(D\cup C_1\cup C_2)]$ contains three disjoint cycles $x_1u_2u_3u_4x_1, v_1x_2x_3yv_1$ and $u_1v_2v_3v_4u_1$ or $x_1u_2u_3u_4x_1, x_2v_1v_2v_3x_2$ and $v_4x_3yu_1v_4$, the last contradiction completes the proof of the main theorem.