betaFeedback

WorksMathematics

An infinite family of bipartite hypotraceable graphs

Abstract

A graph is hypotraceable if it has no Hamiltonian path but every vertex-deleted subgraph does. In 1978, Grötschel asked whether a bipartite hypotraceable graph exists. We resolve this long-standing question in a strong sense by proving that such graphs exist for every sufficiently large even order. Moreover, we show that bipartite hypotraceable graphs can have (1/4+o(1))n2\left(1/4+o(1)\right)n^2 edges, asymptotically attaining the maximum possible number of edges of a bipartite graph, and that there are at least 2(1/4+o(1))n22^{(1/4+o(1))n^2} nonisomorphic examples of order nn, as nn tends to infinity through even integers. Finally, we prove that every bipartite graph occurs as an induced subgraph of a bipartite hypotraceable graph.

Introduction

Hypohamiltonian and hypotraceable graphs have been studied for more than half a century [14, 15]. A graph is Hamiltonian if it contains a spanning cycle, referred to as a Hamiltonian cycle. Similarly, a graph is traceable if it contains a spanning path, referred to as a Hamiltonian path. A graph GG is called hypohamiltonian if GG is not Hamiltonian, but G−vG-v is Hamiltonian for every vertex v∈V(G)v \in V(G). In the current paper, we shall mostly concern ourselves with the related notion of hypotraceable graphs: GG is hypotraceable if it is not traceable, but G−vG-v is traceable for every vertex v∈V(G)v \in V(G).

Initially, the existence of hypotraceable graphs was even conjectured to be impossible, until Horton found an example on 40 vertices in 1973 [19]. Thomassen [15] subsequently proposed a construction to obtain hypotraceable graphs starting from hypohamiltonian graphs, thereby obtaining a smaller example on 34 vertices. He later constructed infinite families of planar and planar cubic examples [16, 17]. Such constructions were further developed in subsequent literature, including the planar examples of Jooyandeh, McKay, Östergård, Pettersson and Zamfirescu [12] and Wiener’s extension using almost hypohamiltonian graphs [19]. These graphs also play a pivotal role in combinatorial optimisation. More precisely, Grötschel [11] showed that certain classes of hypohamiltonian and hypotraceable graphs lead to facet-defining inequalities for the monotone symmetric travelling salesman polytope.

Despite significant attention in the literature on constructing such graphs, the bipartite case has resisted a basic existence question. It is easy to see that a bipartite hypohamiltonian graph cannot exist, because a Hamiltonian cycle in a bipartite graph must use equally many vertices from its two partite sets. For Hamiltonian paths on the other hand, the sizes may differ by one. This leaves the possibility of bipartite hypotraceable graphs open, although their two partite sets must have equal size and their order must therefore be even. In 1978, Grötschel famously asked whether such graphs exist.1

Question 1 (Grötschel, 1978). Does there exist a bipartite hypotraceable graph?

The question appears in Bondy’s chapter in the Handbook of Combinatorics [1 Problem 4.56]. It also appears in Bondy and Murty’s book Graph Theory [3 Appendix A, Problem 92], where it is actually formulated as the conjecture that no such graph exists. This question has continued to motivate work on related spanning structures: Goedgebeur, Renders and Zamfirescu [10] recall this question in their work on bipartite K2K_2-hypohamiltonian graphs. Goedgebeur, Renders, Wiener and Zamfirescu [9] relaxed it in their work on minimum leaf spanning trees and fault-tolerant networks, while Wiener, Yokota and Zamfirescu [20 Problem 4] proposed another relaxation of Grötschel’s question in terms of spanning spiders.

In the current paper, we answer Grötschel’s question affirmatively and thereby disprove the nonexistence conjecture from Bondy and Murty’s book. More precisely, we prove that a bipartite hypotraceable graph exists for every even order n≥200n \ge200. Our examples cover a wide range of sizes, from graphs having 3n/2+103n/2 + 10 edges to graphs having (1/4+o(1))n2(1/4 + o(1))n^2 edges, asymptotically attaining the maximum possible number of edges of a bipartite graph. We also prove that there are at least 2(1/4+o(1))n22^{(1/4+o(1))n^2} nonisomorphic bipartite hypotraceable graphs of order nn, as nn tends to infinity through even integers, and that every bipartite graph occurs as an induced subgraph of some bipartite hypotraceable graph.

Results

An initial building block

Let BB be the cubic bipartite 18-vertex graph shown in Figure 1. This graph appears in the paper by Ellingham and Horton [7], who attribute its use to an earlier construction by Ellingham [6]. This graph has the following useful property.

Figure 1. The 18-vertex cubic bipartite graph BB. No Hamiltonian cycle contains simultaneously the edges w0w1w_0w_1 and cdcd (shown in bold).

Observation 2 (Ellingham and Horton [7]). No Hamiltonian cycle of BB contains both w0w1w_0w_1 and cdcd.

Let DD be the graph that is obtained from BB by subdividing the edge w0w1w_0w_1 two times, thereby replacing it with the path (w0,a,b,w1)(w_0,a,b,w_1). The vertices aa, bb, cc and dd from the graph DD will play a special role and we will refer to these vertices as terminals. The graph DD is a bipartite graph with partite sets A={a,c,u0,u2,u4,v0,v2,v4,w1,w5}A=\{a,c,u_0,u_2,u_4,v_0,v_2,v_4,w_1,w_5\} and B={b,d,u1,u3,u5,v1,v3,v5,w0,w2}B=\{b,d,u_1,u_3,u_5,v_1,v_3,v_5,w_0,w_2\}. We now record several structural properties of DD.

Lemma 3. The following statements hold for the graph DD:

(i) DD contains a Hamiltonian abab-path, a Hamiltonian adad-path, a Hamiltonian cbcb-path, but no Hamiltonian cdcd-path.

(ii) For each two vertex-disjoint paths that together contain all vertices in DD and have aa, bb, cc and dd as their four endpoints, one must be an abab-path and the other one must be a cdcd-path.

(iii) For every z∈Az\in A, the graph D−zD-z has a Hamiltonian bdbd-path, and for every z∈Bz\in B, the graph D−zD-z has a Hamiltonian acac-path.

Proof. We first prove (i). The following three paths are respectively Hamiltonian abab-paths, Hamiltonian adad-paths and Hamiltonian cbcb-paths:

(a,w0,u0,v1,v2,v3,c,u3,u2,w2,w5,u5,u4,d,v4,v5,v0,u1,w1,b)(a,w_0,u_0,v_1,v_2,v_3,c,u_3,u_2,w_2,w_5,u_5,u_4,d,v_4,v_5,v_0,u_1,w_1,b)
(a,b,w1,v1,v2,v3,c,u3,u4,u5,u0,w0,v0,u1,u2,w2,w5,v5,v4,d)(a,b,w_1,v_1,v_2,v_3,c,u_3,u_4,u_5,u_0,w_0,v_0,u_1,u_2,w_2,w_5,v_5,v_4,d)
(c,v3,v2,v1,w1,u1,v0,v5,v4,d,u4,u3,u2,w2,w5,u5,u0,w0,a,b)(c,v_3,v_2,v_1,w_1,u_1,v_0,v_5,v_4,d,u_4,u_3,u_2,w_2,w_5,u_5,u_0,w_0,a,b)

Suppose for the sake of obtaining a contradiction that QQ is a Hamiltonian cdcd-path in DD. Since aa and bb have degree two, this Hamiltonian path must contain the subpath (w0,a,b,w1)(w_0,a,b,w_1). But then one obtains a Hamiltonian cycle of BB by adding the edge cdcd and suppressing aa and bb, which leads to a contradiction by Observation 2 since this cycle contains both w0w1w_0w_1 and cdcd.

Next, we prove (ii). If an acac-path and a bdbd-path are vertex-disjoint and together contain all vertices of DD, then one obtains a Hamiltonian cycle of BB by adding the edges abab and cdcd and suppressing aa and bb. We obtain the same conclusion if there is such an adad-path and a bcbc-path. In both cases, we again obtain a contradiction by Observation 2.

Finally, we prove (iii). By symmetry of DD, it suffices to prove the first statement. The required Hamiltonian bdbd-paths are shown in Table 1.

zzHamiltonian bdbd-path in D−zD-z
aa(b,w1,v1,v2,v3,c,u3,u4,u5,u0,w0,v0,u1,u2,w2,w5,v5,v4,d)(b,w_1,v_1,v_2,v_3,c,u_3,u_4,u_5,u_0,w_0,v_0,u_1,u_2,w_2,w_5,v_5,v_4,d)
cc(b,a,w0,u0,v1,w1,u1,v0,v5,w5,u5,u4,u3,u2,w2,v2,v3,v4,d)(b,a,w_0,u_0,v_1,w_1,u_1,v_0,v_5,w_5,u_5,u_4,u_3,u_2,w_2,v_2,v_3,v_4,d)
u0u_0(b,a,w0,v0,u1,w1,v1,v2,w2,u2,u3,c,v3,v4,v5,w5,u5,u4,d)(b,a,w_0,v_0,u_1,w_1,v_1,v_2,w_2,u_2,u_3,c,v_3,v_4,v_5,w_5,u_5,u_4,d)
u2u_2(b,a,w0,u0,v1,w1,u1,v0,v5,v4,v3,v2,w2,w5,u5,u4,u3,c,d)(b,a,w_0,u_0,v_1,w_1,u_1,v_0,v_5,v_4,v_3,v_2,w_2,w_5,u_5,u_4,u_3,c,d)
u4u_4(b,a,w0,u0,u5,w5,w2,u2,u3,c,v3,v2,v1,w1,u1,v0,v5,v4,d)(b,a,w_0,u_0,u_5,w_5,w_2,u_2,u_3,c,v_3,v_2,v_1,w_1,u_1,v_0,v_5,v_4,d)
v0v_0(b,a,w0,u0,v1,w1,u1,u2,w2,v2,v3,c,u3,u4,u5,w5,v5,v4,d)(b,a,w_0,u_0,v_1,w_1,u_1,u_2,w_2,v_2,v_3,c,u_3,u_4,u_5,w_5,v_5,v_4,d)
v2v_2(b,a,w0,u0,v1,w1,u1,v0,v5,v4,v3,c,u3,u2,w2,w5,u5,u4,d)(b,a,w_0,u_0,v_1,w_1,u_1,v_0,v_5,v_4,v_3,c,u_3,u_2,w_2,w_5,u_5,u_4,d)
v4v_4(b,a,w0,u0,v1,w1,u1,v0,v5,w5,u5,u4,u3,u2,w2,v2,v3,c,d)(b,a,w_0,u_0,v_1,w_1,u_1,v_0,v_5,w_5,u_5,u_4,u_3,u_2,w_2,v_2,v_3,c,d)
w1w_1(b,a,w0,u0,v1,v2,v3,c,u3,u4,u5,w5,w2,u2,u1,v0,v5,v4,d)(b,a,w_0,u_0,v_1,v_2,v_3,c,u_3,u_4,u_5,w_5,w_2,u_2,u_1,v_0,v_5,v_4,d)
w5w_5(b,a,w0,u0,u5,u4,u3,u2,w2,v2,v1,w1,u1,v0,v5,v4,v3,c,d)(b,a,w_0,u_0,u_5,u_4,u_3,u_2,w_2,v_2,v_1,w_1,u_1,v_0,v_5,v_4,v_3,c,d)

Table 1. A Hamiltonian bdbd-path in the graph D−zD-z for every vertex z∈Az \in\mathcal{A}.

Combining building blocks

Next, we will combine two copies of DD and a bipartite graph SS into a new graph having four terminals. This graph SS offers us considerable freedom in our construction, from which we will later derive several interesting consequences.

Let DLD_L and DRD_R be two copies of DD. For every i∈{L,R}i \in\{L,R\}, we denote the terminals of DiD_i by ai,bi,ci,dia_i,b_i,c_i,d_i and its partite sets by Ai\mathcal{A}_i and Bi\mathcal{B}_i. Let SS be a bipartite graph with partite sets UU and WW such that ∣U∣=∣W∣|U|=|W|. We allow SS to have no vertices, in which case U=W=∅U=W=\varnothing. If SS is nonempty, choose vertices xL,xR∈Ux_L,x_R \in U and yL,yR∈Wy_L,y_R \in W satisfying the following conditions:

  • (a) SS has a Hamiltonian xLyRx_Ly_R-path and a Hamiltonian yLxRy_Lx_R-path.

  • (b) For every z∈Uz \in U, the graph S−zS-z has a Hamiltonian yLyRy_Ly_R-path and for every z∈Wz \in W, the graph S−zS-z has a Hamiltonian xLxRx_Lx_R-path.

When SS is nonempty, we require the four chosen vertices xLx_L, xRx_R, yLy_L and yRy_R to be distinct, with one exception: SS is also allowed to be isomorphic to K2K_2, in which case xL=xRx_L=x_R and yL=yRy_L=y_R and the paths in (b) each consist of a single vertex.

If SS is nonempty, define X(S)X(S) by adding the four edges aLyLa_Ly_L, bLxLb_Lx_L, aRyRa_Ry_R and bRxRb_Rx_R to the disjoint union of DLD_L, SS and DRD_R, as shown in Figure 2. If SS is empty, define X(S)=X(∅)X(S)=X(\varnothing) by adding the edges aLbRa_Lb_R and bLaRb_La_R to the disjoint union of DLD_L and DRD_R; this graph has 40 vertices.

Figure 2. A schematic representation of the graph X(S)X(S).

Hence, X(S)X(S) is a bipartite graph with partite sets AX=AL∪U∪ARA_X=A_L\cup U\cup A_R and BX=BL∪W∪BRB_X=B_L\cup W\cup B_R such that ∣AX∣=∣BX∣|A_X|=|B_X|. We call cLc_L, dLd_L, cRc_R and dRd_R the four terminals of X(S)X(S). Note that cL,cR∈AXc_L,c_R\in A_X and dL,dR∈BXd_L,d_R\in B_X.

For every graph SS satisfying the properties mentioned above, the following properties hold for the terminals of X(S)X(S).

Lemma 4. The following statements hold for the graph X(S)X(S):

(i) The only two distinct terminals that occur as endpoints of a Hamiltonian path are {cL,dR}\{c_L,d_R\} and {cR,dL}\{c_R,d_L\}.

(ii) There do not exist two vertex-disjoint paths that together contain all vertices in X(S)X(S) and have cLc_L, dLd_L, cRc_R and dRd_R as their four endpoints.

(iii) For every z∈AXz\in A_X, the graph X(S)−zX(S)-z has a Hamiltonian dLdRd_Ld_R-path, and for every z∈BXz\in B_X, the graph X(S)−zX(S)-z has a Hamiltonian cLcRc_Lc_R-path.

Proof. We first prove (i). Consider a Hamiltonian cLbLc_Lb_L-path in DLD_L and a Hamiltonian aRdRa_Rd_R-path in DRD_R (which exist by Lemma 3(i)). If S=∅S=\varnothing, one obtains a Hamiltonian cLdRc_Ld_R-path by adding the edge bLaRb_La_R. Otherwise, one obtains a Hamiltonian cLdRc_Ld_R-path by adding the edges bLxLb_Lx_L, yRaRy_Ra_R and a Hamiltonian xLyRx_Ly_R-path in SS. Analogously, one can obtain a Hamiltonian cRdLc_Rd_L-path. Since X(S)X(S) is a bipartite graph for which ∣AX∣=∣BX∣|A_X|=|B_X|, the endpoints of a Hamiltonian path must belong to different partite sets and therefore neither {cL,cR}\{c_L,c_R\} nor {dL,dR}\{d_L,d_R\} can be its endpoint set.

To prove (i), we still need to consider the endpoint sets {cL,dL}\{c_L,d_L\} and {cR,dR}\{c_R,d_R\}. The proof of (ii) uses the same argument as the exclusion of these two endpoint sets, so we will treat them together.

Let QQ be a spanning subgraph of X(S)X(S) such that QQ consists of either a Hamiltonian cLdLc_Ld_L-path or of two vertex-disjoint paths with cLc_L, dLd_L, cRc_R and dRd_R as their four endpoints. Both cLc_L and dLd_L have degree one in QQ, while all other vertices of DLD_L have degree two in QQ. Therefore, the sum of the degrees in QQ over all vertices of DLD_L is even. Therefore, QQ must contain an even number of edges with one endpoint in V(DL)V(D_L) and another endpoint in V(X(S))∖V(DL)V(X(S)) \setminus V(D_L). The only two possible such edges are incident with aLa_L and bLb_L.

If QQ contains neither of these two edges, the graph Q[V(DL)]Q[V(D_L)] would be a Hamiltonian cLdLc_Ld_L-path in DLD_L, which is impossible by Lemma 3(i). So QQ contains both of these two edges. This implies in turn that Q[V(DL)]Q[V(D_L)] consists of two vertex-disjoint paths that together contain all vertices of V(DL)V(D_L) and have aLa_L, bLb_L, cLc_L and dLd_L as their four endpoints. Lemma 3(ii) then implies that one of these is an aLbLa_Lb_L-path and the other one is a cLdLc_Ld_L-path. The cLdLc_Ld_L-path must then be a connected component of QQ, since no vertices in this path are incident with an edge that leaves DLD_L. So QQ cannot be a Hamiltonian cLdLc_Ld_L-path in X(S)X(S). Analogously, one can apply the same argument to DRD_R, which shows that a Hamiltonian cRdRc_Rd_R-path in X(S)X(S) cannot exist and this completes the proof of (i).

If QQ consists of two vertex-disjoint paths with cLc_L, dLd_L, cRc_R and dRd_R as their four endpoints, our argument shows that one component is a cLdLc_Ld_L-path contained in DLD_L and another component is a cRdRc_Rd_R-path contained in DRD_R. Neither of these two components contains aLa_L or bLb_L, but then QQ does not contain all vertices of X(S)X(S) and we are done with (ii).

Finally, we prove (iii). We first show that for every z∈AXz \in A_X, the graph X(S)−zX(S)-z has a Hamiltonian dLdRd_Ld_R-path. We first treat the case where z∈ALz \in A_L. There is a Hamiltonian dLbLd_Lb_L-path in DL−zD_L-z by Lemma 3(iii) and a Hamiltonian aRdRa_Rd_R-path in DRD_R by Lemma 3(i). If S=∅S=\varnothing, adding the edge bLaRb_La_R yields the required Hamiltonian dLdRd_Ld_R-path in X(S)−zX(S)-z. If S≠∅S\ne\varnothing, adding the edges bLxLb_Lx_L, yRaRy_Ra_R and a Hamiltonian xLyRx_Ly_R-path in SS yields the required Hamiltonian dLdRd_Ld_R-path in X(S)−zX(S)-z. With a very similar argument, we can deal with the case where z∈ARz \in A_R. We now treat the case where z∈Uz \in U. Then we have S≠∅S\ne\varnothing. The graph S−zS-z has a Hamiltonian yLyRy_Ly_R-path. We can add the edges aLyLa_Ly_L and yRaRy_Ra_R and a Hamiltonian dLaLd_La_L-path in DLD_L and a Hamiltonian aRdRa_Rd_R-path in DRD_R to obtain a Hamiltonian dLdRd_Ld_R-path in X(S)−zX(S)-z.

The second statement of (iii) follows by a completely analogous argument.

The Petersen graph construction

We now combine five of the preceding graphs to obtain bipartite hypotraceable graphs. Let PP be the Petersen graph, using the labels as shown in Figure 3. Consider the perfect matching M={pp′,qq′,rr′,ss′,tt′}M=\{pp',qq',rr',ss',tt'\}. The graph P−MP-M is the disjoint union of two cycles of length five. We orient their edges as p→q→r→s→t→pp \to q \to r \to s \to t \to p and p′→s′→q′→t′→r′→p′p' \to s' \to q' \to t' \to r' \to p'. Let C⃗\vec{C} denote the set of these ten directed edges.

The Petersen graph $P$ with the perfect matching $M$ in bold

Figure 3. The Petersen graph PP with the perfect matching MM in bold.

The following observation can readily be seen.

Observation 5. The subgraph induced by the six endpoints of any three distinct edges of MM contains a cycle of length five.

For each edge e=uv∈Me = uv \in M, consider a graph X(Se)X(S_e) as in Lemma 4 (for some valid choice of a graph SeS_e). The two copies of DD in the graph X(Se)X(S_e) are denoted by DuD_u and DvD_v and we refer to their four terminals as, respectively, au,bu,cu,dua_u, b_u, c_u, d_u and av,bv,cv,dva_v, b_v, c_v, d_v. Therefore, the terminals of X(Se)X(S_e) are cu,du,cv,dvc_u, d_u, c_v, d_v. Note that the five graphs X(Se)X(S_e) do not need to be isomorphic.

Finally, let GG be the graph obtained by taking the disjoint union of these five graphs X(Se)X(S_e) and adding the edge cudvc_u d_v for each directed edge u→vu \to v in C⃗\vec{C}. These ten particular edges are called attachment edges. For each vertex u∈V(P)u \in V(P), the outgoing edge at uu corresponds to an attachment edge incident with cuc_u, whereas the incoming edge at uu corresponds to an attachment edge incident with dud_u. We are now ready to prove the main result of this paper.

Theorem 6. Every graph GG constructed in this way is bipartite and hypotraceable.

Proof. In each graph X(Se)X(S_e), the terminals cu,cvc_u, c_v belong to one partite set and the terminals du,dvd_u, d_v belong to the other partite set. Therefore, GG is bipartite, since every attachment edge is between two vertices belonging to different partite sets.

Suppose for the sake of obtaining a contradiction that GG has a Hamiltonian path QQ. Let M0M_0 consist of all edges e∈Me \in M for which X(Se)X(S_e) contains neither endpoint of QQ. We have ∣M0∣≥3|M_0| \ge3. Let P0P_0 be the subgraph of PP that is induced by all endpoints of edges in M0M_0.

Consider an edge e=uv∈M0e = uv \in M_0. Every vertex of X(Se)X(S_e) must have degree two in QQ. Therefore, an even number of attachment edges of QQ leaves X(Se)X(S_e). This number must be strictly larger than zero, because QQ is connected. There are only four attachment edges incident with X(Se)X(S_e). The graph QQ cannot contain all four attachment edges, because then the graph Q[V(X(Se))]Q[V(X(S_e))] would consist of two vertex-disjoint paths that together contain all vertices in X(Se)X(S_e) and have the four terminals as its endpoints. This is impossible by Lemma 4(ii). Hence, QQ contains exactly two of

these attachment edges. Therefore, Q[V(X(Se))]Q[V(X(S_e))] is a Hamiltonian path in X(Se)X(S_e). The endpoints of this Hamiltonian path are either cu,dvc_u,d_v or du,cvd_u,c_v by Lemma 4(i).

Therefore, for each vertex ww of P0P_0, exactly one of the incoming and outgoing edges of C⃗\vec{C} corresponds to an attachment edge of QQ. We give ww colour 1 if it is the outgoing edge, and colour 0 otherwise. By the preceding paragraph, the endpoints of every edge of M0M_0 have a different colour. If u→v∈C⃗u \to v \in\vec{C} is such that both u∈P0u \in P_0 and v∈P0v \in P_0, then uu has colour 1 if and only if cudv∈E(Q)c_ud_v \in E(Q), which in turn holds if and only if vv has colour 0. The endpoints of every edge of P0P_0 have a different colour, since this edge belongs either to M0M_0 or to P−MP-M. Therefore, P0P_0 is bipartite. But since ∣M0∣≥3\lvert M_0\rvert\ge3, P0P_0 contains a cycle of length five due to Observation 5. We reach a contradiction and therefore GG is not traceable.

Finally, we show that G−zG-z is traceable for every zz in V(G)V(G). Since the five matching edges play symmetric roles in the argument, we may relabel the vertices of the Petersen graph, together with their associated building blocks, so that z∈V(X(Spp′))z \in V(X(S_{pp'})). Consider the following two Hamiltonian paths of PP: Qin=(s,s′,q′,q,r,r′,p′,p,t,t′)Q_{\mathrm{in}}=(s,s',q',q,r,r',p',p,t,t') and Qout=(r,r′,t′,t,s,s′,p′,p,q,q′)Q_{\mathrm{out}}=(r,r',t',t,s,s',p',p,q,q'). Both of these Hamiltonian paths alternate between using one of the five edges of MM and an edge of P−MP-M. The idea is to construct a Hamiltonian path in G−zG-z by replacing every edge of QinQ_{\mathrm{in}} or QoutQ_{\mathrm{out}} by an appropriate path in GG.

If zz is in the same partite set as cpc_p and cp′c_{p'}, we use QinQ_{\mathrm{in}}. The two edges of P−MP-M incident with the edge pp′pp' correspond to attachment edges incident with dpd_p and dp′d_{p'}. Therefore, Lemma 4(iii) yields the existence of a Hamiltonian dpdp′d_pd_{p'}-path in X(Spp′)−zX(S_{pp'})-z. If zz is in the other partite set, we use QoutQ_{\mathrm{out}}. Now the attachment edges are incident with cpc_p and cp′c_{p'} and Lemma 4(iii) yields the existence of a Hamiltonian cpcp′c_pc_{p'}-path in X(Spp′)−zX(S_{pp'})-z.

Now we replace every edge e=uv∈M∖{pp′}e=uv \in M\setminus\{pp'\} of the chosen Hamiltonian path in PP by a Hamiltonian path in X(Se)X(S_e). If ee is not the first and not the last edge on the chosen Hamiltonian path in PP, the required endpoints are one cc-terminal and one dd-terminal, belonging to different copies Du,DvD_u,D_v. Therefore, Lemma 4(i) yields the necessary path. The first and the last edge on the chosen Hamiltonian path in PP both belong to MM. For each of these two edges, let uu be its endpoint incident with the adjacent edge of P−MP-M, and let vv be its other endpoint. If the corresponding attachment edge is incident with cuc_u, choose a Hamiltonian cudvc_ud_v-path in X(Se)X(S_e). If it is incident with dud_u, choose a Hamiltonian ducvd_uc_v-path instead. Both choices are possible by Lemma 4(i). The endpoint in DvD_v becomes an endpoint of the path we are constructing in G−zG-z.

We now have one path covering each of the five graphs X(Se)X(S_e), with zz omitted from X(Spp′)X(S_{pp'}). Join these paths using the four attachment edges corresponding to the edges of P−MP-M on the chosen Hamiltonian path of PP. By construction, each attachment edge joins the appropriate endpoints of two consecutive paths. The resulting path contains every vertex of G−zG-z exactly once and is therefore a Hamiltonian path in G−zG-z.

Consequences

Finally, we draw the reader’s attention to several consequences as a result of the considerable freedom in our construction due to the choice of X(S)X(S). If all five graphs in our construction are chosen as X(∅)X(\varnothing), we obtain a bipartite hypotraceable graph G0G_0 with 200 vertices and 310 edges. This is the smallest graph in our infinite family. If one of these five graphs is replaced by X(S)X(S) (with S≠∅S \ne\varnothing), we obtain a bipartite hypotraceable graph GSG_S with 200+∣V(S)∣200 + |V(S)| vertices and 312+∣E(S)∣312 + |E(S)| edges.

For r≥1r \ge1, let LrL_r be a bipartite graph with partite sets {x1,…,xr}\{x_1,\ldots,x_r\} and {y1,…,yr}\{y_1,\ldots,y_r\} such that xiyj∈E(Lr)x_i y_j \in E(L_r) if and only if ∣i−j∣≤1|i-j| \le1. Choose xL=x1x_L=x_1, xR=xrx_R=x_r, yL=y1y_L=y_1 and yR=yry_R=y_r. The graph LrL_r satisfies conditions (a) and (b): the paths (x1,y1,…,xr,yr)(x_1,y_1,\ldots,x_r,y_r) and (y1,x1,…,yr,xr)(y_1,x_1,\ldots,y_r,x_r) establish the first condition, while (y1,x1,…,yj−1,xj−1,yj,xj+1,yj+1,…,xr,yr)(y_1,x_1,\ldots,y_{j-1},x_{j-1},y_j,x_{j+1},y_{j+1},\ldots,x_r,y_r) is a Hamiltonian y1yry_1y_r-path in Lr−xjL_r-x_j (when j=1j=1 or j=rj=r, the initial or final segment is omitted, respectively). The other paths for the second condition are obtained by exchanging xix_i and yiy_i. All these paths of course still exist whenever an arbitrary set of edges is added and therefore every bipartite graph SS for which LrL_r is a subgraph of SS and SS is a subgraph of Kr,rK_{r,r} yields a valid choice for the graph SS required in Lemma 4. This has the following interesting consequences.

Theorem 7. The following statements hold:

(i) For every even n≥200n \ge200, there is a bipartite hypotraceable graph of order nn with exactly 20 vertices of degree four and all remaining vertices of degree three. For even n≥202n \ge202, every size between 3n/2+103n/2+10 and (n−200)2/4+312(n-200)^2/4+312 is attained.

(ii) As nn tends to infinity through even integers, the maximum size of a bipartite hypotraceable graph of order nn is (1/4+o(1))n2(1/4+o(1))n^2, and the number h(n)h(n) of nonisomorphic such graphs satisfies

h(n)≥2(1/4+o(1))n2.h(n) \ge2^{(1/4+o(1))n^2}.

(iii) Every bipartite graph on s≥1s \ge1 vertices is an induced subgraph of a bipartite hypotraceable graph on 2s+2022s+202 vertices.

Proof. For (i), use G0G_0 when n=200n=200, and otherwise put r=(n−200)/2r=(n-200)/2 and use S=LrS=L_r for the graph GSG_S. The 4⋅5=204 \cdot5=20 terminals have degree four, while all other vertices have degree three. Since ∣E(Lr)∣=3r−2|E(L_r)|=3r-2, adding any number of its missing edges between vertices in distinct partite sets gives every size from 312+3r−2312+3r-2 to 312+r2312+r^2.

For (ii), taking S=Kr,rS=K_{r,r}, where r=(n−200)/2r=(n-200)/2, gives graphs with 312+r2=(1/4+o(1))n2312+r^2=(1/4+o(1))n^2 edges. The density assertion follows from the upper bound n2/4n^2/4 for the size of any bipartite graph of order nn.

For the counting assertion, independently including or omitting each of the r2−3r+2r^2-3r+2 edges outside LrL_r gives 2r2−3r+22^{r^2-3r+2} distinct labelled graphs GSG_S. Each isomorphism class contains at most n!n! labelled graphs, so

h(n)≥2r2−3r+2n!=2(1/4+o(1))n2.(1)h(n) \ge\frac{2^{r^2-3r+2}}{n!}=2^{(1/4+o(1))n^2}. \tag*{(1)}

since r=n/2−100r = n/2 - 100 and log⁡2(n!)=o(n2)\log_2(n!) = o(n^2).

For (iii), let the prescribed graph have partite sets of sizes α\alpha, β\beta, with α+β=s\alpha+ \beta= s, and take r=s+1r = s + 1. The sets A={x1,…,xα}A = \{x_1, \ldots, x_\alpha\} and B={yα+2,…,ys+1}B = \{y_{\alpha+2}, \ldots, y_{s+1}\} (with either set empty when its size is zero) together form an independent set in LrL_r, since j−i≥2j - i \ge2 for every xi∈Ax_i \in A and yj∈By_j \in B. Add the prescribed edges between AA and BB to obtain a graph SS (such that LrL_r is a subgraph of SS and SS is a subgraph of Kr,rK_{r,r}). Thus SS yields a valid choice for the graph SS required in Lemma 4 and GSG_S contains the prescribed graph as an induced subgraph, where ∣V(GS)∣=200+2r=2s+202|V(G_S)| = 200 + 2r = 2s + 202.

We note that Chvátal [5] asked in 1973 whether every graph occurs as an induced subgraph of some hypohamiltonian graph. This question was answered affirmatively by Zamfirescu and Zamfirescu [21]. Hence, Theorem 7(iii) yields an analogous result for bipartite hypotraceable graphs.

Open questions

The search for smaller counterexamples to a conjecture can lead to further structural insights. Tutte [18] famously conjectured that every 3-connected cubic bipartite graph is Hamiltonian. Horton’s 96-vertex counterexample, recorded by Bondy and Murty [2 p. 240], was followed by smaller examples, including the 54-vertex graph of Ellingham and Horton [7]. Georges [8] and Kelmans [13] independently constructed a counterexample on 50 vertices. Brinkmann, Goedgebeur and McKay [4] eventually proved that this Georges–Kelmans graph is a smallest counterexample; they also constructed an infinite family of counterexamples with cyclic edge-connectivity at least five. This progression motivates the corresponding search for smaller bipartite hypotraceable graphs.

Question 8. What is the smallest order of a bipartite hypotraceable graph?

The construction above yields a bipartite hypotraceable graph on 200 vertices. A small modification yields a bipartite hypotraceable graph on 150 vertices, which we describe here without proof. The verification of this smaller example is a bit more cumbersome and we have chosen to instead develop the preceding construction for the sake of clarity of its proof rather than to minimise the order.

Starting from the graph BB in Figure 1, delete the vertices u0u_0 and u1u_1, replace the edges w0w1w_0w_1 and u2u3u_2u_3 by w0u2w_0u_2 and w1u3w_1u_3, and add the edges cw0cw_0, du2du_2 and v0v1v_0v_1. Denote the resulting 16-vertex graph by KK, with terminals a=w1a = w_1, b=u5b = u_5, cc and dd (see Figure 4).

Figure 4. The 16-vertex graph KK, with terminals a=w1a = w_1, b=u5b = u_5, cc and dd.

Take two disjoint copies KLK_L and KRK_R, and identify aLa_L with aRa_R and bLb_L with bRb_R. The resulting 30-vertex graph FF, with terminals cLc_L, dLd_L, cRc_R, dRd_R also satisfies the three conclusions of Lemma 4. Therefore, we can replace each of the five graphs X(Se)X(S_{e}) in the Petersen construction by a copy of FF, yielding a bipartite hypotraceable graph on 150 vertices.

Our second question is motivated by a paper of Thomassen [16]. He constructed infinite families of planar hypotraceable graphs in 1976, while the present paper establishes the existence of bipartite hypotraceable graphs. It is natural to ask whether these two properties can be combined.

Question 9. Does there exist a planar bipartite hypotraceable graph?

Use of AI

The starting point for this work was a bipartite hypotraceable graph obtained over several days of interaction with the AI model Fable 5.2. However, this output provided neither a structural description of the graph nor a conceptual explanation of these properties. The initial proof that this graph was hypotraceable was entirely computer-assisted: a certificate of unsatisfiability for a SAT encoding established non-traceability, while a list of Hamiltonian paths established traceability for each vertex-deleted subgraph. The author subsequently identified the special role of the 18-vertex Ellingham–Horton graph and the Petersen graph, developed alternative constructions of bipartite hypotraceable graphs, and introduced the auxiliary bipartite graph SS in the graph X(S)X(S) that led to the consequences mentioned in this paper. The author also developed, rewrote and simplified the proofs and exposition. AI tools assisted at later stages with proofreading and drafting figures.

References

  1. [1]J. A. Bondy, Basic graph theory: paths and circuits, in R. L. Graham, M. Grötschel and L. Lovász (eds.), Handbook of Combinatorics, Vol. 1, North-Holland, Amsterdam, 1995, pp. 3–110.
  2. [2]J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan, London, 1976.
  3. [3]J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics 244, Springer, London, 2008.
  4. [4]G. Brinkmann, J. Goedegebur and B. D. McKay, The minimality of the Georges–Kelmans graph, Mathematics of Computation 91 (2022), 1483–1500.DOI
  5. [5]V. Chvátal, Flip-flops in hypohamiltonian graphs, Canadian Mathematical Bulletin 16 (1973), 33–41.DOI
  6. [6]M. N. Ellingham, Cycles in 3-connected cubic graphs, M.Sc. thesis, University of Melbourne, 1982.
  7. [7]M. N. Ellingham and J. D. Horton, Non-hamiltonian 3-connected cubic bipartite graphs, Journal of Combinatorial Theory, Series B 34 (1983), 350–353.DOI
  8. [8]J. P. Georges, Non-hamiltonian bicubic graphs, Journal of Combinatorial Theory, Series B 46 (1989), 121–124.DOI
  9. [9]J. Goedgebeur, J. Renders, G. Wiener and C. T. Zamfirescu, Network fault costs based on minimum leaf spanning trees, Applied Mathematics and Computation 525 (2026), 130057.arxiv.org/abs/2502.10213
  10. [10]J. Goedgebeur, J. Renders and C. T. Zamfirescu, Generation and new infinite families of K₂-hypohamiltonian graphs, Discrete Mathematics 347 (2024), 113981.arxiv.org/abs/2311.10593
  11. [11]M. Grötschel, On the monotone symmetric travelling salesman problem: hypohamiltonian/hypotraceable graphs and facets, Mathematics of Operations Research 5 (1980), 285–292.DOI
  12. [12]M. Jooyandeh, B. D. McKay, P. R. J. Östergård, V. H. Pettersson and C. T. Zamfirescu, Planar hypohamiltonian graphs on 40 vertices, Journal of Graph Theory 84 (2017), 121–133.
  13. [13]A. K. Kelmans, Cubic bipartite cyclic 4-connected graphs without Hamiltonian circuits, Russian Mathematical Surveys 43(3) (1988), 205–206.DOI
  14. [14]R. Sousselier, Problème no. 29: Le cercle des irascibles, Revue Française de Recherche Opérationnelle 7 (1963), 405–406.
  15. [15]C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Mathematics 9 (1974), 91–96.DOI
  16. [16]C. Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Mathematics 14 (1976), 377–389.DOI
  17. [17]C. Thomassen, Planar cubic hypohamiltonian and hypotraceable graphs, Journal of Combinatorial Theory, Series B 30 (1981), 36–44.DOI
  18. [18]W. T. Tutte, On the 2-factors of bicubic graphs, Discrete Mathematics 1 (1971), 203–208.DOI
  19. [19]G. Wiener, New constructions of hypohamiltonian and hypotraceable graphs, Journal of Graph Theory 87 (2018), 526–535.DOI
  20. [20]G. Wiener, M. Yokota and C. T. Zamfirescu, Spiders everywhere, Discrete Applied Mathematics 289 (2021), 516–522.DOI
  21. [21]C. T. Zamfirescu and T. I. Zamfirescu, Every graph occurs as an induced subgraph of some hypohamiltonian graph, Journal of Graph Theory 88 (2018), 551–557.DOI

Paper details

vlnc:W_qwr5w794
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Fable 5.2, AI tools

View statement
Looking for related papers…
Contents