Assume an at least $2$-vertex connected, cubic, bipartite, planar graph $G$ that contains a Hamilton cycle (HC) $abcdefg\dots yx\dots za$ (in fact $G$ would then have at least four HCs, see here; it is $yx$ due to the picture I've drawn below and an assumption disproven here). My question is:
How can one deviate from a given Hamilton cycle in such a way, that one introduces exactly two errors, resp. does introducing two errors rely on certain subgraphs?
By errors I mean, that two vertices are met twice, while two others are not met at all.
EDIT: To be a little more specific: The Hamilton cycle and the deviation from it with two errors both start and end at the same vertex and are of the same length. We don't add or remove edges.
With the notation above the HC would be e.g. $adef\color{red}{ef}\dots yx \dots za$, so the $\color{grey}{cd}$-edge is missing. I found three possibilities that are PAINTed below. Let the edges of the HC be coloured in $\color{green}{green}$ and edges that introduce errors in $\color{red}{red}$. $\color{black}{Black}$ edges don't contribute to the case under investigation.
Figure 1: We can introduce two errors if we go directly from $a$ to $d$, thereby miss $bc$, and then:
- use backtracking along the HC $ad\dots ef\color{red}{ef}\dots yx$ $\scriptstyle \text{(this can happen at any edge along the HC)}$
- use backtracking aside the HC $ad\dots e\color{red}{xe}f\dots yx$ $\scriptstyle \text{(this also can happen everywhere on the HC)}$ or
- make a detour at a second square $ad\dots e\color{red}{xy}f\dots yx$ $\scriptstyle \text{(only here we need a 2nd square)}$.
EDIT For Figure 1)ii. I found another version without backtracking:
Let the part of the HC be $\dots abcd\dots ef \dots yx\dots$, so that there is another cycle part $C_{fy}$ joining $f$ and $y$. Then two errors can be introduced as follows:
- make the usual shortcut at a square, missing the $bc$-edge
- go from $e$ to $x$
- walk along $C_{fy}$ in the opposite direction
- again go from $e$ to $x$, which is traversed twice
You may think of backtracking as a $2$-cycle. This variant may also happen everywhere.
Figure 2: "$\color{blue}4$-$\color{goldenrod}2$-hexagon": Again the original HC $\underbrace{abcd}_{\color{blue}4} \dots \underbrace{yx}_{\color{goldenrod}2}$ is depicted in green. Two errors can be introduced by $a\color{red}{xy}d\dots yx$.
My question rephrased:
$\hskip1.3in$ Are these subgraphs the only ones to introduce two errors?
Some remarks:
- In Figure 1 the vertices $d$ and $e$ don't need to be adjacent as indicated by the dashed line.
In both figures, I think (not sure) that I could have also chosen $yx$ at the end.- I tried to use the "$2$-$2$-$2$-hexagon" (where Hamilton runs through like $ab...cd...yx$, so without the $bc$-, $dy$- and $xa$-edges) without success
- and sorry for the PAINT work (feel free to improve it!)...
.. and I'm pretty sure that the answer is no, see below...
EDIT: Some more remarks concerning a general solution
I also thought about a more general approach by using $n$th powers of adjacency (sub)matrices, which corresponds to doing $n$ steps on the subgraphs. It's even possible to exclude backtracking as you can read here.
But since the the set of adjacency (sub)matrices, i.e. the (sub)graphs sould be the result of such an approach, I admit that for now, I don't know how to work this out. How does the HC come into play then?
Thanks for your help and special thanks to Brian Rushton,...