On cycle lengths in graphs of moderate degree

NEW

Problem: Reconstructed statement: in finite simple undirected graphs, every Hamiltonian bipartite graph $G$ on $n$ vertices with minimum degree $\delta$ and

has a cycle of length $2\ell$ for every integer $2\le \ell\le n/2$. This is exactly the supplied Conjecture 1.12; it asserts bipancyclicity under the stated degree/order bound.

Result: The conjecture is false.

Construct a bipartite graph $G$ with parts

where $|A_i|=|B_i|=2$ and $|P_i|=3$. Add edges as follows:

• every vertex of $P_i$ is adjacent to all four vertices of $A_i\cup B_i$;
• $q_i$ is adjacent to all vertices of $B_i\cup A_{i+1}$;
• there are no other edges.

Then $|X|=|Y|=12$, so $n=24$. Every vertex has degree $4$, hence $\delta=4$, and

The graph is Hamiltonian. If $A_i=\{a_i^1,a_i^2\}$, $B_i=\{b_i^1,b_i^2\}$, and $P_i=\{p_i^1,p_i^2,p_i^3\}$, then

is a Hamiltonian cycle.

It remains to show that $G$ has no $10$-cycle. Call a connector $q_i$ crossing on a cycle if its two cycle-neighbors lie one in $B_i$ and one in $A_{i+1}$. Traversing any cycle, the block index changes exactly at crossing connectors. Since the crossing connectors form an even subgraph of the triangle on block indices $\mathbb Z_3$, either none are crossing or all three are crossing.

If none are crossing, the cycle stays inside one block $A_i\cup B_i$, possibly using its two incident connectors as extra $Y$-vertices. It then uses at most the four $X$-vertices in that block, so its length is at most $8$.

If all three connectors are crossing, then inside each block the cycle contains a path from $q_{i-1}$ to $q_i$. These two connectors attach to disjoint pairs $A_i$ and $B_i$, so such a path has length at least $4$. Thus the whole cycle has length at least $3\cdot4=12$.

Hence no cycle has length $10$. But the conjecture requires a cycle of length $2\ell=10$ for $\ell=5$. Therefore the conjecture is disproved.

This is not a boundary or vacuous failure: the counterexample is $4$-regular, Hamiltonian, bipartite, and satisfies the strict inequality with room to spare.

Citation: No published disproof is used here. Original source: H. Bencherif Ait-Djafer, “On cycle lengths in graphs of moderate degree,” Discrete Mathematics 125 (1994), 55–62.