Criticality of Counterexamples to Toroidal Edge-Hamiltonicity

Abstract

A well-known conjecture of Grünbaum and Nash-Williams proposes that $4$-connected toroidal graphs are Hamiltonian. The corresponding results for $4$-connected planar and projective-planar graphs were proved by Tutte and by Thomas and Yu, respectively, using induction arguments that proved a stronger result, that every edge is on a Hamilton cycle. However, this stronger property does not hold for $4$-connected toroidal graphs: Thomassen constructed counterexamples. Thus, the standard inductive approach will not work for the torus. One possible way to modify it is by characterizing the situations where some edge is not on a Hamilton cycle. We provide a contribution in this direction, by showing that the obvious generalizations of Thomassen’s counterexamples are critical in a certain sense.

1 Introduction

The study of Hamilton cycles for graphs on surfaces was begun in 1931 by Whitney [18], who showed that $4$-connected planar triangulations are Hamiltonian. Tutte [16, 17] later generalized this to all $4$-connected planar graphs. Thomassen [14] (with a minor correction by Chiba and Nishizeki [3]) further extended this by showing that $4$-connected planar graphs are Hamilton-connected. Thomas and Yu [11] showed that $4$-connected projective-planar graphs are Hamiltonian. Kawarabayashi and Ozeki [6] outline a proof that $4$-connected projective-planar graphs are Hamilton-connected.

In this paper we will be concerned with the following conjecture.

Conjecture 1.1

(Grünbaum [5] and Nash-Williams [10]) Every $4$-connected toroidal graph is Hamiltonian.

A number of partial results are known. Altshuler [1] showed that $6$-connected toroidal graphs, which are $6$-regular triangulations with a grid structure, are Hamiltonian. In the same paper he also showed that $4$-connected toroidal quadrangulations, which are $4$-regular with a grid structure, are Hamiltonian. Brunet and Richter [2] proved that $5$-connected toroidal triangulations are Hamiltonian, and this was generalized by Thomas and Yu [12] to all $5$-connected toroidal graphs. Thomas et al. [13] showed that every $4$-connected toroidal graph has a Hamilton path. In [7], Kawarabayashi and Ozeki outline a proof that all $4$-connected toroidal triangulations are Hamiltonian. Recently some special classes of toroidal graphs, including $4$-connected toroidal graphs with toughness exactly $1$, were shown to be Hamiltonian by Nakamoto and Ozeki and by those two authors with Fujisawa [4, 9]. However, a complete proof of Conjecture 1.1 still seems a long way off.

One reason Conjecture 1.1 seems difficult to prove is that the standard inductive approach used for the plane and projective plane cannot be extended to the torus. The results for $4$-connected planar and projective-planar graphs in [11, 16, 17] are essentially proved by strengthening the result in two ways, to enable induction to be used. The first strengthening is to look for what are known as Tutte cycles instead of Hamilton cycles, in $2$-connected graphs instead of $4$-connected graphs. In the $4$-connected case a Tutte cycle must be a Hamilton cycle. Some additional control over the Tutte cycles is needed, and so the second strengthening is to make sure that the Tutte cycle can use any given edge on a designated ‘boundary’ of the graph. For $4$-connected planar or projective-planar graphs, therefore, this means that they are not just Hamiltonian but edge-Hamiltonian: every edge has a Hamilton cycle through it. This property does not extend to the torus, however, as $4$-connected toroidal graphs are not in general edge-Hamiltonian; hence the same type of inductive arguments fail.

Examples of non-edge-Hamiltonian $4$-connected toroidal graphs were given by Thomassen [14]. He observed that the cartesian product of two even cycles yields a bipartite $4$-connected quadrangulation of the torus, and if a diagonal (an edge between opposite vertices) is added in any quadrangle, then that diagonal cannot be in a Hamilton cycle. This construction is easily generalized. Take any bipartite $4$-connected toroidal quadrangulation $Q$, say with a bipartition into black and white vertices. As mentioned earlier, $Q$ has a grid structure, which we discuss in more detail later. It also has equally many black and white vertices. In each quadrangle we can add either a black–black or white–white diagonal, specifying the color of its ends. For any nonempty subset of the quadrangles, add a black–black diagonal across each quadrangle. Then the resulting $4$-connected toroidal graph does not have a Hamilton cycle through any of the added diagonals. We will call these grid-type examples.

Even more generally, we can take a bipartite quadrangulation of the torus in which there are equally many black and white vertices, and all white vertices have degree $4$. There may be black vertices of degree $2$ or $3$, so the connectivity may be less than $4$. However, it may be possible to make the graph $4$-connected by adding black-black diagonals in some quadrangles. The added diagonals will again not be on a Hamilton cycle. In Fig. 1 the solid edges form a quadrangulation of the torus (represented in the usual way, as a rectangle with opposite sides identified) that is only $2$-connected. The addition of the four diagonals (dashed edges) makes it $4$-connected, but the diagonals are not on any Hamilton cycle. These examples, however, are much harder to characterize than the grid-type examples.

Fig. 1

Non-grid example

Because of these examples, the inductive approach used for planar and projective-planar graphs cannot be used for the torus without modification. A suitable modification might be to prove a result saying that every $2$-connected toroidal graph has a Tutte cycle through any boundary edge, except when a specific structure resulting from a bipartite subgraph occurs. Before trying to prove such a result, however, it seems sensible to obtain some evidence as to whether the problem (lack of edge-Hamiltonicity) disappears when we depart even slightly from the bipartite situation. In this paper we address this by showing that the grid-type examples are critical, in the sense that adding even one white-white diagonal, in addition to the already added black-black diagonals, restores edge-Hamiltonicity. Our main theorem is therefore as follows.

Theorem 1.2

Let $G$ be a 4-connected, 4-regular, bipartite simple graph on the torus with partition sets of white and black vertices. If we add a nonempty set $E_1$ of one or more black-black diagonals to $G$, then no element of $E_1$ lies on a Hamilton cycle in $G \cup E_1$. However, if we add one further white-white diagonal $e_2$ in a quadrangle of $G \cup E_1$ then each edge of $G \cup E_1 \cup \{e_2\}$ lies on a Hamilton cycle of that graph.

The proof of this result makes up Sect. 2, and in Sect. 3 we give some concluding remarks.

Fig. 2

Case 1.1

2 Proof of the Main Result

Most of the proof of Theorem 1.2 is accomplished by the following proposition.

Proposition 2.1

Let $G$ be a 4-connected, 4-regular, bipartite simple graph on the torus with partition sets of white and black vertices. Suppose we add a black–black diagonal $e_1$ in one quadrangle of $G$, and a white–white diagonal $e_2$ in a different quadrangle. Then the resulting graph has a Hamilton cycle that uses both $e_1$ and $e_2$.

Proof

By Euler’s formula, we know that all 4-regular, bipartite graphs on the torus are quadrangulations. As is well known [1, 8, 15] $4$-regular quadrangulations of the torus (bipartite or not) can be described (not necessarily uniquely) by three integer parameters $m \ge 1$ (width), $n \ge 1$ (height) and $q$ (shift). To construct the quadrangulation we will denote $Q(m,n;q)$, take an $m$-vertex path $P_m$ with vertex set ${\mathbb {Z}}_m = \{0, 1, 2, \ldots , m-1\}$ and an $n$-vertex cycle $C_n$ with vertex set ${\mathbb {Z}}_n = \{0, 1, 2, \ldots , n-1\}$ (vertices labeled in the obvious order in each case). Representing the torus as a rectangle with opposite sides identified, embed the cartesian product $P_m \times C_n$ with the copies of $P_m$ horizontal and the copies of $C_n$ vertical. Vertices are identified by ordered pairs $(i,j)$ with $i \in {\mathbb {Z}}_m$ and $j \in {\mathbb {Z}}_n$, and we specify edges and paths by concatenated ordered pairs. We place vertex $(0,0)$ at bottom left, and $(m-1,n-1)$ at top right. In the cylindrical face between cycles $\{m-1\} \times C_n$ and $\{0\} \times C_n$ add edges $(m-1, j)(0, j+q)$ for $j \in {\mathbb {Z}}_n$ (so only the value of $q$ modulo $m$ matters). For example, Fig. 2a, b show $Q(10,8;2)$ with additional diagonals $e_1, e_2$.

Each $Q(m, n; q)$ has an automorphism $U$ (translation up) which maps every $(i,j) \mapsto (i, j+1)$, and an automorphism $R$ (translation right) which maps $(i,j) \mapsto (i+1,j)$ for $i \ne m-1$ and $(m-1, j) \mapsto (0, j+q)$. There are also isomorphisms $F_1, F_2$ (reflections) from $Q(m, n; q)$ to $Q(m, n; -q)$: $F_1$ is a reflection about the horizontal line corresponding to points $(i,0)$ and maps $(i,j) \mapsto (i,-j)$, and $F_2$ is a reflection about a central vertical line in our standard picture of the torus, and maps $(i,j) \mapsto (m-1-i, j)$.

Now $G=Q(m,n;q)$ for some $m$, $n$ and $q$. Since $G$ is bipartite, $n$ must be even. Since $G$ is simple, $n \ge 4$, and there are restrictions on $q$ if $m = 1$ or $2$, which we discuss later. In the toroidal embedding of $G$, number the columns of faces $0, 1, 2, \ldots , m-1$, so that column $i$ consists of faces between $\{i-1\} \times C_n$ and $\{i\} \times C_n$. Similarly, number the rows of faces $0, 1, 2, \ldots , n-1$ so that row $j$ consists of faces between $P_m \times \{j-1\}$ and $P_m \times \{j\}$ (faces in column $0$ do not have a row number).

Case 1 Suppose that $m \ge 3$, or that $m=2$ and $e_1$ and $e_2$ are in the same column. By applying a suitable power of $R$ we can assume that neither $e_1$ nor $e_2$ is in column $0$, and at least one of them is in column $1$. Without loss of generality suppose $e_1$ is in column $1$. By applying a suitable power of $U$ we can make one end of $e_1$ be $(0,0)$. Then, applying $F_1$ if necessary (which negates $q$, but the value of $q$ will not matter in Case 1), we can assume that $e_1 = (0,0)(1,1)$.

Now let $c$ and $r$ be respectively the column and row of the face for which $e_2$ is a diagonal. We have ensured that $c\ne 0$, but possibly $r= 0$.

Case 1.1 Suppose $r\ge 2$. If $c$ is even, then we can find a Hamilton cycle through $e_1$ and $e_2$ as shown in Fig. 2a; this works even if $r=2$ or $c=2$ or both, and regardless of whether $r$ is odd or even.

If $c=m-1$ then we replace the subpath on the right which joins $(c,0)$ to $(c,1)$ by the single edge $(m-1,0)(m-1,1)$. This subpath is an example of a horizontal zigzag: a path which is the union of horizontal paths of the form $(i_1,j)(i_1+1,j)\dots (i_2,j)$ for fixed $i_1$ and $i_2$ and cyclically consecutive values of $j$, together with vertical edges to join the horizontal paths into a single path. In addition, a horizontal zigzag may include an extra horizontal edge at each end of the path.

If $c$ is odd and $r\ge 3$ then we can find a Hamilton cycle through $e_1$ and $e_2$ as shown in Fig. 2b; this works even if $c=1$, and regardless of whether $r$ is odd or even. If $c=1$ and $r=2$ we modify column $1$ as shown in Fig. 2c. If $c\ge 3$ is odd and $r= 2$ we modify column $c$ as shown in Fig. 2d. If $c=m-1$ in any of these cases then we replace the horizontal zigzag on the right which joins $(c,0)$ to $(c,n-1)$ by the edge $(m-1,0)(m-1,n-1)$.

Fig. 3

Cases 1.2 and 1.3

Case 1.2 Suppose $r= 1$. Then $c\ge 2$ and $m \ge 3$. We have a Hamilton cycle through $e_1$ and $e_2$ as shown in Fig. 3a. If $c=2k$ is even then we use the path $(2k-1,0)(2k,1)(2k,0)(2k+1,0)$, and if $c=2k+1$ is odd then we use the path $(2k-1,0)(2k,0)(2k,1)(2k+1,0)$. This works even if $c=2$. If $c$ is even and $c= m-1$ then we replace the horizontal zigzag which joins $(c,0)$ to $(c,n-1)$ by the edge $(m-1,0)(m-1,n-1)$. If $c$ is odd then the original construction works even if $c=m-1$.

Case 1.3 Suppose $r= 0$. If $c$ is even then $e_2$ has the form $(c-1,0)(c,n-1)$. We apply $U$ then $R^{m-1-c}$ then $F_2$, which move $e_2$ to $(c-1,1)(c,0)$ then to $(m-2,1)(m-1,0)$ then to $(1,1)(0,0)=e_2'$. These move $e_1$ to $(0,1)(1,2)$ then to $(m-1-c,1)(m-c,2)$ then to $(c,1)(c-1,2)=e_1'$. Now $e_1'$ is not in column $0$ or row $0$ so we can apply an earlier case to $e_2'$ and $e_1'$, replacing $e_1$ and $e_2$ respectively.

So $c$ is odd. Then we can find a Hamilton cycle through $e_1$ and $e_2$ as shown in Fig. 3b. If $c=m-1$ then we replace the horizontal zigzag on the right which joins $(c,n-1)$ to $(c,n-2)$ by the edge $(m-1,n-1)(m-1,n-2)$. This works even if $c=1$.

Fig. 4

Cases 2 and 3.1

Case 2 Suppose that $m=2$ and $e_1$ and $e_2$ are in different columns. Without loss of generality suppose $e_1$ is in column $1$ and $e_2$ is in column $0$. By applying an appropriate power of $U$, and possibly $F_2$, we can move $e_1$ so that $e_1 = (0,0)(1,1)$. Then $e_2 = (0,i)(1,j)$ where $i$ is odd and $j$ is even and $0 \le i,j \le n-1$. There are slightly different pictures depending on the order of $i$ and $j$. Figure 4a shows the Hamilton cycle through $e_1$ and $e_2$ for $i<j$, and Fig. 4b is for $i>j \ge 2$. The case $i> j = 0$ is treated as $i < j=n$, using Fig. 4a with the path $\ldots (0,i)(1,j=n=0)(1,n-1)(1,n-2)\ldots (1,i+1)(0,i+1)(0,i+2)(0,i+3)\ldots (0,n=0)(1,1)\ldots$.

Case 3 Suppose that $m=1$. Then $G$ has a single vertical cycle $C=C_n$ containing all vertices, and we identify vertices with elements of ${\mathbb {Z}}_n$. We write edges and paths as comma-separated sequences of vertices inside parentheses, and to indicate a cycle we use double parentheses, so that for example $C=(\!(0, 1, 2, \ldots , n-1)\!)$. An edge $(i,j)$ with $j-i = \pm k$ (mod $n$), $2 \le k \le n/2$, is called a $k$-chord, or just a chord. $G$ is a circulant graph containing edges of $C$ and all possible $q$-chords. The added diagonals $e_1$ and $e_2$ are $(q \pm 1)$-chords. Two chords $(i,j)$ and $(k,\ell )$ cross if $i, j, k, \ell$ are distinct and appear in the order $i, k, j, \ell$, or its reverse, along $C$.

Since $G$ is bipartite, $n$ is even and $q$ must be odd. Since $G$ is simple, $q \ne 0, 1, -1$ or $n/2$ (mod $n$). Moreover, $Q(1,n;q)$ is identical to $Q(1,n;-q=n-q)$ (both embeddings have the same underlying graphs and facial cycles) and so we may assume that $3 \le q < n/2$. Thus, $n \ge 2q+2 \ge 8$. We may assume that $e_1$ is a $k_1$-chord and $e_2$ is a $k_2$-chord, where $k_1 \ge k_2$ and $k_1, k_2 \in \{q-1, q+1\}$.

For this case it is difficult to use our standard picture of the embedding on the torus. With only one column of vertices, the desired cycle may use many of the edges crossing column $0$, which makes it difficult to follow. Thus, for this case we will use two alternative representations.

Case 3.1 Suppose $e_1$ and $e_2$ cross. Using automorphisms of $G$, we may suppose that $e_1 = (0, k_1)$ and $e_2 = (a, b=a+k_2)$ where $1 \le a \le k_1-1$ and $k_1+1 \le b \le k_1+k_2-1$.

In this case we break the cycle $C$ into two segments, depicted as vertical paths, so straight vertical edges are edges of $C$. Straight horizontal edges represent $q$-chords $(i,i+q)$ with $i$ at left, $i+q$ at right. Other edges must be identified using their endvertices. Quadrangles bounded by horizontal and vertical edges represent faces in the embedding, although we do not see all faces in our picture.

If $k_1 = q+1$ then $1 \le a \le q$ and $q+2 \le b \le 2q+1 \le n-1$, and we have a Hamilton cycle through $e_1$ and $e_2$ as shown in Fig. 4c, using either $(a-1,a+q-1,a+q,a,a+q+1,a+1)$ if $k_2=q+1$, or $(a-1,a+q-1,a,a+q,a+q+1,a+1)$ if $k_2=q-1$.

If $k_1 = q-1$ then $k_2 = q-1$ also. Then $1 \le a \le q-2$ and $q \le b \le 2q-3 < n-1$. We have the Hamilton cycle shown in Fig. 4d.

Case 3.2 Suppose $e_1$ and $e_2$ do not cross. Note that $e_1$ and $e_2$ have no common vertex because one is a black–black diagonal and the other is a white–white diagonal. Using automorphisms of $G$, we may suppose that $e_1 = (0, k_1)$ and $e_2 = (a, b=a+k_2)$ where $a \ge k_1+1$ and $k_1+k_2+1 \le b \le n-1$. Regard all vertices as nonnegative integers $i$ with $0 \le i \le n-1$, so that we can order them.

In this case we will draw $C$ as a circle so the other edges are literally chords of this circle. The general pattern is to divide the vertices up into cycles by taking $q+1$ consecutive vertices along the circle and closing up the cycle with a chord. The added diagonals $e_1$ and $e_2$ give cycles of length $q+2$ or $q$. Next these cycles are connected by choosing an edge $f=(i,i+1)$ of $C$ in one cycle and an edge $f'=(j,j+1)$ in the next cycle, so that $g=(i,j)$ and $g'=(i+1,j+1)$ are $q$-chords, and removing $f$ and $f'$, and then replacing them by $g$ and $g'$, to merge the two cycles together. Leftover vertices are incorporated using a similar strategy, and eventually everything is merged into a single cycle. Care must be taken so that edges of a cycle used for one purpose (such as linking to the previous cycle) do not overlap with those used for another purpose (such as linking to the next cycle, or to leftover vertices).

Recall that $q$ is odd, so $k_1, k_2 = q \pm 1$ are even. Also, $e_1$ is a black–black edge while $e_2$ is a white–white edge, so $a$ is odd. Let $C_1 = (\!(0, 1, 2, \ldots , k_1)\!)$ and let $C_2 = (\!(a, a+1, a+2, \ldots , a+k_2)\!)$. Consider the vertices along $C$ after $C_1$ but before $C_2$, which we wish to partition into $(q+1)$-cycles as far as possible. For each integer $i$ let $x_i = k_1 + 1 + i(q+1)$ and let $p = \max \{i \;|\; x_i \le a\}$; then $p \ge 0$. We have $p$ $(q+1)$-cycles $D_0, D_1, \ldots , D_{p-1}$ where $D_i = (\!(x_i, x_i+1, \ldots , x_i+q=x_{i+1}-1)\!)$. This leaves vertices $x_p, x_p+1, \ldots , a-1$: since $x_p$ and $a$ are both odd, there are an even number of these, from which we form a (possibly empty) matching $M = \{(x_p, x_p+1), (x_p+2,x_p+3), \ldots , (a-2,a-1)\}$.

In a similar way we let $y_i = a+k_2+1 + i(q+1)$, $r = \max \{i \;|\; y_i \le n\} \ge 0$ and divide the vertices along $C$ after $C_2$ but before $C_1$ into $r$ $(q+1)$-cycles $E_0, E_1, \ldots E_{r-1}$, where $E_i = (\!(y_i, y_i+1, \ldots , y_i+q = y_{i+1}-1)\!)$. Since $y_r$ and $n$ are both even, there are an even number of leftover vertices from which we form a (possibly empty) matching $N = \{(y_r, y_r+1), (y_r+2, y_r+3), \ldots , (n-2, n-1)\}$. So as we go along $C$ the vertices are partitioned into a sequence of subgraphs $\mathcal {S}= C_1, D_0, D_1, \ldots , D_{p-1}, M, C_2, E_0, E_1, \ldots , E_{r-1}, N$ (omitting $M$ or $N$ if they are empty). We need to merge these into a single Hamilton cycle that uses $e_1$ and $e_2$.

Given an edge $(i, i+1)$, the edges $(i+q, i+q+1)$ and $(i-q,i-q-1)$ are called its forward and backward mates, respectively. If we have two vertex-disjoint cycles $Z$ containing $(i,i+1)$ and $Z'$ containing its mate $(i+q, i+q-1)$ then we may combine them into a new cycle $Z \cup Z' - \{(i,i+1),(i+q,i+q+1)\} \cup \{(i,i+q), (i+1, i+q+1)\}$. We call this a cycle-to-cycle link, or CC-link. If we have a cycle $Z$ containing $(i,i+1)$, and its forward mate $(i+q,i+q+1)$ is vertex-disjoint from $Z$ (this mate will be an edge in one of the matchings $M$ or $N$), then we may combine them into a new cycle $Z - (i,i+1) \cup (i,i+q,i+q+1,i+1)$. We may apply a similar operation using the backward mate $(i-q,i-q+1)$. We call this a cycle-to-edge link, or CE-link.

Our basic idea is to link together consecutive subgraphs in the sequence $\mathcal {S}$ using CC- and CE-links. An edge of $C$ belonging to a subgraph of $\mathcal {S}$ is forward-linking if its forward mate is in the next subgraph of $\mathcal {S}$, and backward-linking if its backward mate is in the previous subgraph of $\mathcal {S}$. To avoid conflicts between forward- and backward-linking edges we classify an edge $e=(i,i+1)$ of $C$ as odd or even according to whether $i$, its smaller end, is odd or even, respectively. Note that a mate of $e$ is odd when $e$ is even, and vice versa, because $q$ is odd. In each cycle of $\mathcal {S}$ we will use odd edges to link in one direction and even edges to link in the opposite direction.

Suppose we have two consecutive cycles $Z, Z'$ in $\mathcal {S}$. We may write $Z = (\!(i-s, i-s+1, \ldots , i)\!)$ and $Z'=(\!(i+1, i+2, \ldots , i+t+1)\!)$ where $s, t \in \{q-1, q, q+1\}$. Because $q \ge 3$ and $s, t \ge q-1$, $Z \cap C$ always contains the two edges $(i-2,i-1)$ and $(i-1,i)$, and they are always forward-linking because $Z'$ always contains their forward mates $(i+q-2,i+q-1)$ and $(i+q-1,i+q)$. Therefore we always have both an odd forward-linking edge of $Z$ mated with an even backward-linking edge of $Z'$, and an even forward-linking edge of $Z$ mated with an odd backward-linking edge of $Z'$.

Suppose we have a matching $L$ preceded by a cycle $Z$ in $\mathcal {S}$. We may write $Z = (\!(i-s, i-s+1, \ldots , i)\!)$ and $L = \{(i+1, i+2), (i+3, i+4), \ldots , (i+t-1, i+t)\}$ where $s \in \{q-1, q, q+1\}$ and $t$ is even with $2 \le t \le q-1$. Now if $(i+j, i+j+1)$ is an edge of $L$ then $1 \le j \le t-1 \le q-2$, so that $i-s \le i+1-q \le i+j-q$ and $i+j+1-q \le i-1$, which shows that the backward mate $(i+j-q,i+j+1-q)$ is in $Z$. Thus, every edge of $L$ is backward-linking. Similarly, if a matching $L$ is followed by a cycle in $\mathcal {S}$, then every edge of $L$ is forward-linking.

Fig. 5

Case 3.2.2

Case 3.2.1 Suppose $M = \emptyset$. Use odd forward-linking edges and even backward-linking edges and repeated CC-linking to combine all of $C_1, D_0, D_1, \ldots , D_{p-1}, C_2, E_0, \ldots , E_{r-1}$ into a single cycle $Z_1$. Then $Z_1$ still contains all odd edges of the last cycle ($E_{r-1}$, or $C_2$ if $r=0$) so these can be used to incorporate all edges of $N$ (if any), which are even, by repeated CE-linking to give the final Hamilton cycle $H$. Since we delete only edges of $C$ when linking, $H$ contains the chords $e_1$ from $C_1$ and $e_2$ from $C_2$, as required.

Case 3.2.2 Suppose $M \ne \emptyset$. We form a cycle $H_2$ containing all vertices of $C_2, E_0, E_1, \ldots , E_{r-1}$ and $N$ as in Case 3.2.1. Note that $H_2$ contains all even edges of $C_2$. In a similar way, but switching the roles of odd and even edges, we form a cycle $H_1$ containing all vertices of $C_1, D_0, D_1, \ldots , D_{p-1}$ and $M$. $H_1$ contains all edges of $M$, which are odd. We can now CC-link $H_1$ and $H_2$ using the first edge of $M$, $(x_p,x_p+1)$, and its even forward mate in $C_2$, to form a Hamilton cycle $H$. As before, $H$ contains $e_1$ and $e_2$.

This process is illustrated in Fig. 5, where we have $n = 30$, $q=5$, $k_1=4$, $p=2$, $k_2=4$, $r=0$ and $|M|=|N|=2$. In Fig. 5a we show a schematic of where the links are added: CC-links are given by solid lines, and CE-links by lines that are dashed at the matching end (to indicate that the matching edge is not deleted). In Fig. 5b we show the corresponding Hamilton cycle $H$. No edge of $C$ is used by two CC-links, but the first edge of $M$, $(x_p, x_p+1)$, is used by both a CE-link and a CC-link.

This concludes the proof of Proposition 2.1. $\square$

Now we prove our main result, which we restate.

Theorem 1.2. Let $G$ be a 4-connected, 4-regular, bipartite simple graph on the torus with partition sets of white and black vertices. If we add a nonempty set $E_1$ of one or more black-black diagonals to $G$, then no element of $E_1$ lies on a Hamilton cycle in $G \cup E_1$. However, if we add one further white-white diagonal $e_2$ in a quadrangle of $G \cup E_1$ then each edge of $G \cup E_1 \cup \{e_2\}$ lies on a Hamilton cycle of that graph.

Proof

Let $e$ be an edge of $G' = G \cup E_1 \cup \{e_2\}$. Suppose first that $e \in E(G)$. We use the notation developed in the proof of Proposition 2.1. If $m \ge 2$ then, since $n$ is even, it is easy to construct a Hamilton cycle in $G$ consisting of a vertical path with ends joined by a horizontal zigzag, which uses at least one vertical and one horizontal edge. Since $e$ is either vertical or horizontal (including edges across column $0$), and all vertical edges are similar in $G$ and all horizontal edges are similar in $G$, we can use an automorphism of $G$ to find a Hamilton cycle of $G$, and hence of $G'$, through $e$. If $m=1$ then, using the notation from Case 3 of the above proposition, $G$ has a Hamilton cycle $(\!(0, q, q-1, q-2, \ldots , 2, 1, q+1, q+2, q+3, \ldots , n-1)\!)$ which uses both vertical edges (edges of $C$) and horizontal edges ($q$-chords). Again, $e$ is either vertical or horizontal, and using an automorphism of $G$ we can find a Hamilton cycle through $e$.

So suppose $e \in E_1$, or $e = e_2$. If $e \in E_1$ we let $e' = e_2$, and if $e = e_2$ we choose any $e' \in E_1$. By Proposition 2.1 there is a Hamilton cycle through $e$ and $e'$ in $G \cup \{e,e'\}$ and hence in $G'$. $\square$

3 Conclusion

Our results provide some evidence that bipartiteness is the underlying factor preventing $4$-connected toroidal graphs from being edge-Hamiltonian. Unfortunately, we had to restrict ourselves to examining graphs derived from the grid-type examples. For other examples, such as that shown in Fig. 1, we do not have a good structure theorem, and it is difficult even to know if a graph constructed by adding diagonals to a bipartite quadrangulation of the torus is $4$-connected.

However, something at least is known about bipartite quadrangulations of the torus. The graphs we are interested in are bipartite quadrangulations that can yield a $4$-connected graph with the addition of diagonals on one side of the bipartition (say, black-black diagonals). It is not difficult to show that this can happen only if all white vertices have degree exactly $4$. Fujisawa et al. [4] recently showed that bipartite quadrangulations of the torus in which all white vertices have degree $4$ are Hamiltonian, satisfying Conjecture 1.1, as long as they are at least $3$-connected. Perhaps their techniques may yield some results on edge-Hamiltonicity after diagonals are added.

There is also a similar conjecture to Conjecture 1.1 for the Klein bottle, and similar counterexamples to edge-Hamiltonicity, based on $4$-connected bipartite quadrangulations of the Klein bottle. A characterization of such quadrangulations is known [8, 15], but it is significantly more complicated than for the torus, and the quadrangulations themselves are not as symmetric as those on the torus, meaning that many more cases would have to be examined to obtain a result similar to Theorem 1.2.