Minimum degree conditions
for the existence of a sequence of cycles
whose lengths differ by one or two

All graphs considered in this paper are finite undirected graphs without loops or multiple edges. For a graph $G$, we denote by $V(G)$ and $E(G)$ the vertex set and the edge set of $G$, respectively, and $\deg_{G}(v)$ denotes the degree of a vertex $v$ in $G$.

In 1983, Thomassen proposed the following two conjectures.

The above conjectures originated from the conjecture of Burr and Erdős concerning the extremal problem for the existence of cycles with prescribed lengths modulo $k$ (see [2]). We refer the reader to [4] for more details. In 2018, Liu and Ma proved that Conjectures A and B are true for all even integers $k$ by considering the existence of a sequence of paths whose lengths differ by two in bipartite graphs, see [4, Theorem 1.9].

Recently, Gao, Huo, Liu and Ma [6] announced that they had confirmed Conjectures A and B for all integers $k$ by using the following theorem. Here, we say that a sequence of $k$ paths (or $k$ cycles) $P_{1},\dots,P_{k}$ is admissible if $|E(P_{1})|\geq 2$, and either $|E(P_{i+1})|-|E(P_{i})|=1$ for $1\leq i\leq k-1$ or $|E(P_{i+1})|-|E(P_{i})|=2$ for $1\leq i\leq k-1$.

In this paper, we show that the degree condition in Theorem C can be relaxed as follows.

This study also originated from the question of whether every graph of minimum degree at least three contains two admissible cycles, which was raised by Erdős (see [1]). In 1998, Bondy and Vince answered this queston by proving the following stronger theorem.

They also conjectured that every graph of sufficiently large order, having at most $m$ vertices of degree less than three, contains two admissible cycles, and they gave some remarks for the case of small $m$. In 2020, Gao and Ma [3] settled the conjecture in the affirmative for all $m$.

We give the following another generalization of Theorem D by using Theorem 1.

Note that a weaker version of Theorem 2 is obtained from Theorem C (see [6, Theorem 1.3]), and the result (and also Theorem 2) settles Conjectures A and B for all integers $k$.

To show Theorem 1, in the next section, we consider the existence of admissible paths in “rooted graphs” and give a stronger result than Theorem 1 (see Theorem 3 in Section 2). We also extend the concept of “cores” which were used in the argument of [4, 6] in preparation for the proof of Theorem 3. In Section 3, we prove Theorem 3 and also give the proof of Theorem 2 at the end of Section 3.

(2) Since $\delta(G,x,y;z)\geq k+1\geq 3$, we have $|V(G)|\geq 4$. Suppose that $|V(G)|=4$. Note that, then $\delta(G,x,y;z)=k+1=3$. Let $u$ and $v$ be two distinct vertices of $V(G)\setminus\{x,y\}$ such that $u\neq z$. Since $\deg_{G}(u)=3$, we have $N_{G}(u)=\{x,y,v\}$. By (R2), we also have $N_{G}(v)\cap\{x,y\}\neq\emptyset$, say $xv\in E(G)$ up to symmetry, and then $xuy$ and $xvuy$ are $k\ (=2)$ admissible $(x,y)$-paths, a contradiction. $\quad\square$

(2) Suppose that $xv\in E(G)$ for some $v\in\{y,z\}$, and choose such a vertex $v$ so that $v=y$ if possible. If $G-xv$ (i.e., the graph obtained from $G$ by deleting the edge $xv$) is $2$-connected, then by the induction hypothesis, it follows that $G-xv$ (and also $G$) contains $k$ admissible $(x,y)$-paths, a contradiction. Thus $G-xv$ is not $2$-connected. Since $G$ is $2$-connected by Claim 3.2 (1), this implies that $(G-xv,x,v)$ is a $2$-connected rooted graph with exactly two end-blocks.

Let $B_{1},\dots,B_{t}$ ($t\geq 2$) be all the blocks of $G-xv$ such that $V(B_{i})\cap V(B_{i+1})\neq\emptyset$ for $1\leq i\leq t-1$, say $V(B_{i})\cap V(B_{i+1})=\{b_{i}\}$ for $1\leq i\leq t-1$. Without loss of generality, we may assume that $x\in V(B_{1})\setminus\{b_{1}\}$ and $v\in V(B_{t})\setminus\{b_{t-1}\}$. Then $y\in V(B_{p})\setminus\{b_{p-1}\}$ for some $p$ with $1\leq p\leq t$, where we let $b_{0}=x$.

Suppose that $p=t$. Then $(G-xv,x,y;z)$ is a $2$-connected rooted graph such that $\delta(G-xv,x,y;z)=\delta(G,x,y;z)$. Hence, by the induction hypothesis, $G-xv$ (and also $G$) contains $k$ admissible $(x,y)$-paths, a contradiction. Thus $p\leq t-1$. This implies that $v\neq y$, that is, $v=z$. Then by the choice of $v$, we have $xy\notin E(G)$.

Let $G^{\prime}=G[\bigcup_{1\leq i\leq p}V(B_{i})]$, and let $z^{\prime}=b_{p}$. Note that $z\notin V(G^{\prime})$. Note also that if $p=1$, then since $xy\not\in E(G)$, $V(G^{\prime})\setminus\{x,y,z^{\prime}\}=V(B_{1})\setminus\{x,y,b_{1}\}\neq\emptyset$ holds; if $p\geq 2$, $V(G^{\prime})\setminus\{x,y,z^{\prime}\}\neq\emptyset$ clearly holds. Then $(G^{\prime},x,y;z^{\prime})$ is a $2$-connected rooted graph such that $\delta(G^{\prime},x,y;z^{\prime})\geq\delta(G,x,y;z)$, and so the the induction hypothesis yields that $G^{\prime}$ (and also $G$) contains $k$ admissible $(x,y)$-paths, a contradiction. Thus $xv\notin E(G)$ for each $v\in\{y,z\}$. By the symmetry of $x$ and $y$, we also have $yz\notin E(G)$. $\quad\square$

By Remark 1 and Claim 3.2, there exist cores with respect to $(x,y)$ and $(y,x)$, respectively, in $G$. By the symmetry of $x$ and $y$, we can rename the vertices $x$ and $y$ so that

1. (X​Y1)

   there exists a core $H$ with respect to $(x,y)$ so that the number of type of $H$ is as small as possible,

2. (X​Y2)

   $\deg_{G}(x)\leq\deg_{G}(y)$, subject to (X​Y1), and

3. (X​Y3)

   $\textup{dist}_{G}(x,z)\leq\textup{dist}_{G}(y,z)$, subject to (X​Y1) and (X​Y2).

Let $H$ be an $\ell$-core with respect to $(x,y)$ in $G$ for some integer $\ell$, and let $C$ be the component of $G-V(H)$ such that $y\in V(C)$. Choose $H$ so that

1. (H1)

   the number of type of $H$ is as small as possible, and

2. (H2)

   subject to (H1),

   1. (H2-1)

      if $H$ is of type 1 or type 2, then $|T|$ is maximum;

   2. (H2-2)

      if $H$ is of type 3, then (i) $|S|$ is maximum, (ii) $|T|$ is maximum, subject to (i).

   3. (H2-3)

      If $H$ and $C$ satify the following condition (H2)((H2-3))(T):

      1. (T)

         $H$ is of type 3, $|T|\geq 3$, $V(C)=\{y\}$, $N_{G}(x)=N_{G}(y)=T$, and there exists a component $D_{0}$ of $G-V(H)$ such that $D_{0}\not=C$, $V(D_{0})\setminus\{z\}\neq\emptyset$ and $N_{G}(D_{0})\cap T\not=\emptyset$,

      then let $t_{0}\in N_{G}(D_{0})\cap T\ ({}\cap N_{G}(y))$, and we modify $H$ (and $C$ depending on $H$) by resetting $\ell$, $S$ and $T$ as follows:

      1. (M1)

         if $|T|=|S|+1$¹¹1Note that, in this case, $\ell\geq 2$., then let $s_{0}\in S$, and we reset $\ell:=\ell-1$, $S:=S\setminus\{s_{0}\}$ and $T:=T\setminus\{t_{0}\}$;

      2. (M2)

         if $|T|\geq|S|+2$, then we reset $\ell:=\ell$, $S:=S$ and $T:=T\setminus\{t_{0}\}$.

Note that if we modify $H$ as in (H2)(H2-3), then the new graph $H$ is also an $\ell$-core of type 3 with respect to $(x,y)$ (see also Figure 3). However, to make the difference clear, we sometimes say that $H$ is of type 3^♭ if $H$ is modified as above; otherwise $H$ is of type 3^♮.

Assume first that $H$ is of type 1. If $|N_{G}(v)\cap V(H)|\geq\ell+2$, then we have $N_{G}(v)\cap V(H)=x\cup T$, which contradicts the maximality of $T$ (see (H2)(H2-1)). Thus $|N_{G}(v)\cap V(H)|\leq\ell+1$. If the equality holds, we clearly have $N_{G}(v)\cap T\not=\emptyset$, since $\ell+1\geq 2$.

Assume next that $H$ is of type 2, and suppose that $|N_{G}(v)\cap V(H)|\geq\ell+2$. Since there exists no core of type 1 with respect to $(x,y)$ by (H1), we have $x\not\in N_{G}(v)$ or $N_{G}(v)\cap S=\emptyset$. Since $|N_{G}(v)\cap V(H)|\geq\ell+2$, $|S|=2$ and $|T|=\ell$, this yields that $N_{G}(v)\cap V(H)=S\cup T$, which contradicts the maximality of $T$ (see (H2)(H2-1)). Thus $|N_{G}(v)\cap V(H)|\leq\ell+1$. If the equality holds, then since $x\not\in N_{G}(v)$ or $N_{G}(v)\cap S=\emptyset$ holds, it follows that $|N_{G}(v)\cap T|=(\ell+1)-|N_{G}(v)\cap(x\cup S)|\geq(\ell+1)-2=\ell-1\geq 1$. Thus we have $N_{G}(v)\cap T\not=\emptyset$.

Assume finally that $H$ is of type 3. Suppose that $|N_{G}(v)\cap V(H)|\geq\ell+1$. Since there exists no core of type 1 with respect to $(x,y)$ by (H1), we have $x\not\in N_{G}(v)$ or $N_{G}(v)\cap T=\emptyset$. Since there also exists no core of type 2 with respect to $(x,y)$ by (H1), we have $|N_{G}(v)\cap T|\leq 1$ or $N_{G}(v)\cap S=\emptyset$. If $H$ is of either type 3^♮ or type 3^♭ in (H2)((H2-3))(M2), then $|N_{G}(v)\cap T|\leq\ell+1$ (by (H2)(H2-2)-(i)); if $H$ is of type 3^♭ in (H2)((H2-3))(M1), then we have $|N_{G}(v)\cap T|\leq|T|=\ell+1$. If $H$ is of type 3^♮, then $x\cup S\not\subseteq N_{G}(v)$ (by (H2)(H2-2)-(ii)); if $H$ is of type 3^♭, then since $N_{G}(x)=T\cup\{t_{0}\}$ and $v\not=t_{0}$, we have $x\cup S\not\subseteq N_{G}(v)$. Since $|S|=\ell$, combining these facts yields that $|N_{G}(v)\cap V(H)|=\ell+1$, and $N_{G}(v)\cap T\neq\emptyset$. $\quad\square$

By Claim 3.2 (2) and (H2)((H2-3))(T), we can easily obtain the following.

We now divide the proof into two cases according to $V(C)=\{y\}$ or $V(C)\neq\{y\}$.

Note that by Claim 3.4, $H$ is not of type 3^♭.

Assume first that $H$ is of type 1. Then $|N_{G}(y)\cap T|\geq 2$, and so there exists a core of type 1 with respect to $(y,x)$. Since $N_{G}(y)\subseteq T\subseteq N_{G}(x)$, it follows from (X​Y2) that $N_{G}(x)=N_{G}(y)=T$. Thus the claim follows.

Assume next that $H$ is of type 2. Since $|N_{G}(y)\cap V(H-x)|\geq 2$, and since there exists no core of type 1 with respect to $(y,x)$ by (X​Y1), we have $N_{G}(y)=S$. This in particular implies that $y\vee S\vee T$ is an $\ell$-core of type 2 with respect to $(y,x)$. Since $N_{G}(y)=S\subseteq N_{G}(x)$, it follows from (X​Y2) that $N_{G}(x)=N_{G}(y)=S$. Thus the claim follows.

Assume finally that $H$ is of type 3. By (X​Y1) and (H1), there exist no cores of type 1 or type 2 with respect to $(y,x)$, and so any core with respect to $(y,x)$ is of type $3$ (by Remark 1, Claim 3.2). This also implies that $N_{G}(y)\subseteq T$ or $N_{G}(y)\subseteq S$. Since $|T|\geq\max\{\ell+1,2\}>\ell=|S|$ and $T\subseteq N_{G}(x)$, it follows from (X​Y2) that $N_{G}(x)=N_{G}(y)=T$. Thus the claim follows. $\quad\square$

By Claim 3.5, $N_{G}(x)=N_{G}(y)=T$. By Claim 3.6, we also have $V(G)=T\cup\{x,y,z\}$. Since $|T|=\ell+1\leq k-1$ by Fact 3 (2), and since $T\setminus\{z\}\neq\emptyset$, the degree condition yields that $(\ell+1=)\ |T|=k-1$, $z\notin T\cup\{x,y\}$, and $N_{G}(v)=(T\setminus\{v\})\cup\{x,y,z\}$ for all $v\in T$. This implies that $G$ contains $(x,y)$-paths of lengths $2,3,\ldots,k+1$. Thus $G$ contains $k$ admissible $(x,y)$-paths, a contradiction.