Two Steps away from the Hamilton Cycle

Question

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:

1. use backtracking along the HC $ad\dots ef\color{red}{ef}\dots yx$ $\scriptstyle \text{(this can happen at any edge along the HC)}$
2. 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
3. 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,...

Answer 1

Just to clarify, it seems like you want your deviation to result in an edge path still (no jumping from one vertex to another). Is that right? In fact, it seems you want a closed edge path, one that starts and stops at the same vertices.

When you introduce your first kind of error (missing two vertices completely), you have to remove three line segments, the ones going into, between, and out of the pair of points (call them $a$ and $b$). Removing these breaks the closed circuit into a single arc, whose end points must be connected by some new path to form a new closed circuit. Any such path will either:

1. Go directly from $a$ to $b$, or
2. Go through some even number of other points on the way to $b$ (even by bipartiteness).

In case 1, the three deleted edges and the new edge start and end at the same points, and so they form a simple closed curve separating the plane. So we get a square, possibly with part of the graph inside and part outside. I do not know if your conditions prevent this possibility. We then need to go through two vertices an extra time. So we can only do this by adding a new edge somewhere. We can either follow this new edge by its inverse, and continue onward (I.e. backtracking) or not. If not, call the vertex we labded at x. We must go over some subsequent edge to a point y. However, I believe your figure 3 is false, as x and y need not be connected by an edge of the Hamiltonian cycle. In any case, this can't go on forever, as we can't visit any other vertex twice, so we must return immediately to the place where we left off (f in your picture). As above, this does give a square, although it may be non-empty inside.

In case 2, our new path can only go through two other vertices, since otherwise we added too many errors. Thus, we must have a hexagon, although, again, some of the grah might be inside of the hexagon and some outside.

So, the only things not covered by your pictures are:

1. The square/hexagon might contain parts of the graph inside and outside at the same time.
2. The new edge added between x and y might not be an edge in the old Hamiltonian cycle.

This proof method should generalize easily, although I haven't thought it through. Adding twice as many errors either gives copies of the above errors, or octagon errors, etc. I may post more. Thanks for sharing your problem! Let me know if there are any problems in my analysis.

Answer 2

Ok, I think one can split the problem into two parts on two subgraphs:

1. Miss two vertices and
2. meet two vertices twice.

This was already indicated in Fig.1, where the upper square subgraph was always the same and only the lower one varied. When you miss two vertices, the number of edges used in that subgraph drops by two as well ( two additional edges are used in the "meet twice" case).

I think I found another way to miss two vertices:

Combine this with, let's say backtracking or any other option to meet vertices twice from the question's figure 1 (edit: or the example below). I think is really different from the way above shown, since the vertices that are missing are not connected by an edge as above.

Let the 10-vertex-Hamiltonian path be $abcdefghij$, then the two error variant is 8 vertices long and may be written as $afghicdj$. It should be possible to extend the inner hexagon to larger structures by introducing additional edges into the outer squares.

EDIT

Here's another example of how to meet two vertices twice:

Let the part of the HC be $abcd$, then the path on the rhs is $abadcd$, where $a$ and $d$ are met twice. The difference to example 1.iii.(lower part) is the HC we start out with.

So the above shown are not the only onces...

---

Now for something analytical. Think of $A$ as the adjacencey matrix of the subgraph with $n$ vertices (without the black edges going out of the subgraph itself, so it might not be cubic anylonger, which is not important for the moment). A Hamilton path would need $n$ steps to traverse it. Starting from $\vec {v_{start}}=(1,0,0,\dots ,0)^T$ we get $\vec{v_{final=n}}=A^n\vec{v_0}=(a_1,a_2,\dots,a_n)^T$ where $a_k$ denotes the number of ways from the starting vertices to vertex $k$. So $a_n$ would contain the Hamiltonian paths next to other paths that reach vertex $n$ in $n$, but maybe don't touch all other points.

To miss two vertices wee need to check if it's possible to reach $n$ after $n-2$ steps as well and meanwhile meet $n-2$ vertices. Similar for the "meet twice" case.

Instead of using $A^n$, one could use propagation without backtracking (see here), to get rid of some of the obsolete paths (at least in the "missing" case, in the "meeting" case backtracking should be allowed), but, all in all and after all I personally think that one has to check infinitely large subgraphs for the property sketched above, which is not possible in finite time.

The question remains, if these are all possible subgraphs if the largest face degree is $6$?