# How many edges can be added to two circles before the graph becomes Hamiltonian?

Start with two $n$-circles $(v_1\cdots v_n)$ and $(w_1\cdots w_n)$ of vertice sets $V$ and $W$, where $n\ge 5$. Add a number of vertex-disjoint edges between $V$ and $W$ (thus no chords) in a way that the resulting graph is still non-Hamiltonian. What is the maximum number $f(n)$ of such edges (let us call them links) that can be added? Equivalently:

How many edges can a non-Hamiltonian graph on $2n$ vertices with two induced $n$-cycles and maximal degree 3 have?

Obviously such a graph cannot contain a $C_4$. Thus, if in a construction there is an edge $(v_i,w_j)$, the four edges $(v_{i\pm1},w_{j\pm1})$ are excluded.

It is clear that $f(n)$ grows linearly with $n$: a trivial lower bound is $f(n)\ge [\frac n2]$, realized by adding the links $(v_{2i},w_{2i})$ for $i=1,\dots,[\frac n2]$.

What can be said about $\lim\limits_{n\to\infty}\dfrac {f(n)}n$? Or at least about $\liminf\limits_{n\to\infty}\dfrac {f(n)}n$ and $\limsup\limits_{n\to\infty}\dfrac {f(n)}n$?

The Petersen graph shows that $f(5)=5$, and it is not hard to see that $f(6)<6$, thus $f(6)=5$ by the left displayed graph where the circles are $abcde\!f$ and $123456$. Further $f(8)\ge6$ by the right graph. To see that it is not Hamiltonian, note that the two violet edges cannot belong to a H-circle.

I have also found $f(9)\ge 7$ and generally $f(2k-5)\ge k$ for $k\ge7$ by "splitting" two vertices of the Petersen graph, but as $k$ grows, this is no big improvement on the trivial lower bound. Yet, there should be much better lower bounds.
As for upper bounds, I suppose they are notoriously hard to find. Is it possible at least to prove that $f(n)<n$ for $n\ge 6$? Equivalently, that for each $\sigma \in S_n$ the 3-regular graph with links $(v_i,w_{\sigma(i)})$ is Hamiltonian? Note that the Generalized Petersen Graph $GP(7,2)\simeq GP(7,3)$, the most "symmetric" instance of those graphs, is already Hamiltonian, which makes me conjecture this holds.

If a full set of $n$ edges is inserted between the cycles, what you have is a "cycle permutation graph". According to this paper, there are nonhamiltonian cycle permutation graphs for all odd $n\ge 9$. I don't know what is known for even $n$.
• @GerhardPaseman Yes that should work, so it guarantees $f(n)\ge n-1$ for even $n\ge10$. Jul 6, 2016 at 10:12