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 edges, asymptotically attaining the maximum possible number of edges of a bipartite graph, and that there are at least nonisomorphic examples of order , as 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 is called hypohamiltonian if is not Hamiltonian, but is Hamiltonian for every vertex . In the current paper, we shall mostly concern ourselves with the related notion of hypotraceable graphs: is hypotraceable if it is not traceable, but is traceable for every vertex .
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 -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 . Our examples cover a wide range of sizes, from graphs having edges to graphs having edges, asymptotically attaining the maximum possible number of edges of a bipartite graph. We also prove that there are at least nonisomorphic bipartite hypotraceable graphs of order , as 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 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 . No Hamiltonian cycle contains simultaneously the edges and (shown in bold).
Observation 2 (Ellingham and Horton [7]). No Hamiltonian cycle of contains both and .
Let be the graph that is obtained from by subdividing the edge two times, thereby replacing it with the path . The vertices , , and from the graph will play a special role and we will refer to these vertices as terminals. The graph is a bipartite graph with partite sets and . We now record several structural properties of .
Lemma 3. The following statements hold for the graph :
(i) contains a Hamiltonian -path, a Hamiltonian -path, a Hamiltonian -path, but no Hamiltonian -path.
(ii) For each two vertex-disjoint paths that together contain all vertices in and have , , and as their four endpoints, one must be an -path and the other one must be a -path.
(iii) For every , the graph has a Hamiltonian -path, and for every , the graph has a Hamiltonian -path.
Proof. We first prove (i). The following three paths are respectively Hamiltonian -paths, Hamiltonian -paths and Hamiltonian -paths:
Suppose for the sake of obtaining a contradiction that is a Hamiltonian -path in . Since and have degree two, this Hamiltonian path must contain the subpath . But then one obtains a Hamiltonian cycle of by adding the edge and suppressing and , which leads to a contradiction by Observation 2 since this cycle contains both and .
Next, we prove (ii). If an -path and a -path are vertex-disjoint and together contain all vertices of , then one obtains a Hamiltonian cycle of by adding the edges and and suppressing and . We obtain the same conclusion if there is such an -path and a -path. In both cases, we again obtain a contradiction by Observation 2.
Finally, we prove (iii). By symmetry of , it suffices to prove the first statement. The required Hamiltonian -paths are shown in Table 1.
| Hamiltonian -path in | |
Table 1. A Hamiltonian -path in the graph for every vertex .
Combining building blocks
Next, we will combine two copies of and a bipartite graph into a new graph having four terminals. This graph offers us considerable freedom in our construction, from which we will later derive several interesting consequences.
Let and be two copies of . For every , we denote the terminals of by and its partite sets by and . Let be a bipartite graph with partite sets and such that . We allow to have no vertices, in which case . If is nonempty, choose vertices and satisfying the following conditions:
(a) has a Hamiltonian -path and a Hamiltonian -path.
(b) For every , the graph has a Hamiltonian -path and for every , the graph has a Hamiltonian -path.
When is nonempty, we require the four chosen vertices , , and to be distinct, with one exception: is also allowed to be isomorphic to , in which case and and the paths in (b) each consist of a single vertex.
If is nonempty, define by adding the four edges , , and to the disjoint union of , and , as shown in Figure 2. If is empty, define by adding the edges and to the disjoint union of and ; this graph has 40 vertices.
Figure 2. A schematic representation of the graph .
Hence, is a bipartite graph with partite sets and such that . We call , , and the four terminals of . Note that and .
For every graph satisfying the properties mentioned above, the following properties hold for the terminals of .
Lemma 4. The following statements hold for the graph :
(i) The only two distinct terminals that occur as endpoints of a Hamiltonian path are and .
(ii) There do not exist two vertex-disjoint paths that together contain all vertices in and have , , and as their four endpoints.
(iii) For every , the graph has a Hamiltonian -path, and for every , the graph has a Hamiltonian -path.
Proof. We first prove (i). Consider a Hamiltonian -path in and a Hamiltonian -path in (which exist by Lemma 3(i)). If , one obtains a Hamiltonian -path by adding the edge . Otherwise, one obtains a Hamiltonian -path by adding the edges , and a Hamiltonian -path in . Analogously, one can obtain a Hamiltonian -path. Since is a bipartite graph for which , the endpoints of a Hamiltonian path must belong to different partite sets and therefore neither nor can be its endpoint set.
To prove (i), we still need to consider the endpoint sets and . The proof of (ii) uses the same argument as the exclusion of these two endpoint sets, so we will treat them together.
Let be a spanning subgraph of such that consists of either a Hamiltonian -path or of two vertex-disjoint paths with , , and as their four endpoints. Both and have degree one in , while all other vertices of have degree two in . Therefore, the sum of the degrees in over all vertices of is even. Therefore, must contain an even number of edges with one endpoint in and another endpoint in . The only two possible such edges are incident with and .
If contains neither of these two edges, the graph would be a Hamiltonian -path in , which is impossible by Lemma 3(i). So contains both of these two edges. This implies in turn that consists of two vertex-disjoint paths that together contain all vertices of and have , , and as their four endpoints. Lemma 3(ii) then implies that one of these is an -path and the other one is a -path. The -path must then be a connected component of , since no vertices in this path are incident with an edge that leaves . So cannot be a Hamiltonian -path in . Analogously, one can apply the same argument to , which shows that a Hamiltonian -path in cannot exist and this completes the proof of (i).
If consists of two vertex-disjoint paths with , , and as their four endpoints, our argument shows that one component is a -path contained in and another component is a -path contained in . Neither of these two components contains or , but then does not contain all vertices of and we are done with (ii).
Finally, we prove (iii). We first show that for every , the graph has a Hamiltonian -path. We first treat the case where . There is a Hamiltonian -path in by Lemma 3(iii) and a Hamiltonian -path in by Lemma 3(i). If , adding the edge yields the required Hamiltonian -path in . If , adding the edges , and a Hamiltonian -path in yields the required Hamiltonian -path in . With a very similar argument, we can deal with the case where . We now treat the case where . Then we have . The graph has a Hamiltonian -path. We can add the edges and and a Hamiltonian -path in and a Hamiltonian -path in to obtain a Hamiltonian -path in .
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 be the Petersen graph, using the labels as shown in Figure 3. Consider the perfect matching . The graph is the disjoint union of two cycles of length five. We orient their edges as and . Let denote the set of these ten directed edges.

Figure 3. The Petersen graph with the perfect matching in bold.
The following observation can readily be seen.
Observation 5. The subgraph induced by the six endpoints of any three distinct edges of contains a cycle of length five.
For each edge , consider a graph as in Lemma 4 (for some valid choice of a graph ). The two copies of in the graph are denoted by and and we refer to their four terminals as, respectively, and . Therefore, the terminals of are . Note that the five graphs do not need to be isomorphic.
Finally, let be the graph obtained by taking the disjoint union of these five graphs and adding the edge for each directed edge in . These ten particular edges are called attachment edges. For each vertex , the outgoing edge at corresponds to an attachment edge incident with , whereas the incoming edge at corresponds to an attachment edge incident with . We are now ready to prove the main result of this paper.
Theorem 6. Every graph constructed in this way is bipartite and hypotraceable.
Proof. In each graph , the terminals belong to one partite set and the terminals belong to the other partite set. Therefore, is bipartite, since every attachment edge is between two vertices belonging to different partite sets.
Suppose for the sake of obtaining a contradiction that has a Hamiltonian path . Let consist of all edges for which contains neither endpoint of . We have . Let be the subgraph of that is induced by all endpoints of edges in .
Consider an edge . Every vertex of must have degree two in . Therefore, an even number of attachment edges of leaves . This number must be strictly larger than zero, because is connected. There are only four attachment edges incident with . The graph cannot contain all four attachment edges, because then the graph would consist of two vertex-disjoint paths that together contain all vertices in and have the four terminals as its endpoints. This is impossible by Lemma 4(ii). Hence, contains exactly two of
these attachment edges. Therefore, is a Hamiltonian path in . The endpoints of this Hamiltonian path are either or by Lemma 4(i).
Therefore, for each vertex of , exactly one of the incoming and outgoing edges of corresponds to an attachment edge of . We give colour 1 if it is the outgoing edge, and colour 0 otherwise. By the preceding paragraph, the endpoints of every edge of have a different colour. If is such that both and , then has colour 1 if and only if , which in turn holds if and only if has colour 0. The endpoints of every edge of have a different colour, since this edge belongs either to or to . Therefore, is bipartite. But since , contains a cycle of length five due to Observation 5. We reach a contradiction and therefore is not traceable.
Finally, we show that is traceable for every in . 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 . Consider the following two Hamiltonian paths of : and . Both of these Hamiltonian paths alternate between using one of the five edges of and an edge of . The idea is to construct a Hamiltonian path in by replacing every edge of or by an appropriate path in .
If is in the same partite set as and , we use . The two edges of incident with the edge correspond to attachment edges incident with and . Therefore, Lemma 4(iii) yields the existence of a Hamiltonian -path in . If is in the other partite set, we use . Now the attachment edges are incident with and and Lemma 4(iii) yields the existence of a Hamiltonian -path in .
Now we replace every edge of the chosen Hamiltonian path in by a Hamiltonian path in . If is not the first and not the last edge on the chosen Hamiltonian path in , the required endpoints are one -terminal and one -terminal, belonging to different copies . Therefore, Lemma 4(i) yields the necessary path. The first and the last edge on the chosen Hamiltonian path in both belong to . For each of these two edges, let be its endpoint incident with the adjacent edge of , and let be its other endpoint. If the corresponding attachment edge is incident with , choose a Hamiltonian -path in . If it is incident with , choose a Hamiltonian -path instead. Both choices are possible by Lemma 4(i). The endpoint in becomes an endpoint of the path we are constructing in .
We now have one path covering each of the five graphs , with omitted from . Join these paths using the four attachment edges corresponding to the edges of on the chosen Hamiltonian path of . By construction, each attachment edge joins the appropriate endpoints of two consecutive paths. The resulting path contains every vertex of exactly once and is therefore a Hamiltonian path in .
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 . If all five graphs in our construction are chosen as , we obtain a bipartite hypotraceable graph with 200 vertices and 310 edges. This is the smallest graph in our infinite family. If one of these five graphs is replaced by (with ), we obtain a bipartite hypotraceable graph with vertices and edges.
For , let be a bipartite graph with partite sets and such that if and only if . Choose , , and . The graph satisfies conditions (a) and (b): the paths and establish the first condition, while is a Hamiltonian -path in (when or , the initial or final segment is omitted, respectively). The other paths for the second condition are obtained by exchanging and . All these paths of course still exist whenever an arbitrary set of edges is added and therefore every bipartite graph for which is a subgraph of and is a subgraph of yields a valid choice for the graph required in Lemma 4. This has the following interesting consequences.
Theorem 7. The following statements hold:
(i) For every even , there is a bipartite hypotraceable graph of order with exactly 20 vertices of degree four and all remaining vertices of degree three. For even , every size between and is attained.
(ii) As tends to infinity through even integers, the maximum size of a bipartite hypotraceable graph of order is , and the number of nonisomorphic such graphs satisfies
(iii) Every bipartite graph on vertices is an induced subgraph of a bipartite hypotraceable graph on vertices.
Proof. For (i), use when , and otherwise put and use for the graph . The terminals have degree four, while all other vertices have degree three. Since , adding any number of its missing edges between vertices in distinct partite sets gives every size from to .
For (ii), taking , where , gives graphs with edges. The density assertion follows from the upper bound for the size of any bipartite graph of order .
For the counting assertion, independently including or omitting each of the edges outside gives distinct labelled graphs . Each isomorphism class contains at most labelled graphs, so
since and .
For (iii), let the prescribed graph have partite sets of sizes , , with , and take . The sets and (with either set empty when its size is zero) together form an independent set in , since for every and . Add the prescribed edges between and to obtain a graph (such that is a subgraph of and is a subgraph of ). Thus yields a valid choice for the graph required in Lemma 4 and contains the prescribed graph as an induced subgraph, where .
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 in Figure 1, delete the vertices and , replace the edges and by and , and add the edges , and . Denote the resulting 16-vertex graph by , with terminals , , and (see Figure 4).
Figure 4. The 16-vertex graph , with terminals , , and .
Take two disjoint copies and , and identify with and with . The resulting 30-vertex graph , with terminals , , , also satisfies the three conclusions of Lemma 4. Therefore, we can replace each of the five graphs in the Petersen construction by a copy of , 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 in the graph 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]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]J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan, London, 1976.
- [3]J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics 244, Springer, London, 2008.
- [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]V. Chvátal, Flip-flops in hypohamiltonian graphs, Canadian Mathematical Bulletin 16 (1973), 33–41.DOI
- [6]M. N. Ellingham, Cycles in 3-connected cubic graphs, M.Sc. thesis, University of Melbourne, 1982.
- [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]J. P. Georges, Non-hamiltonian bicubic graphs, Journal of Combinatorial Theory, Series B 46 (1989), 121–124.DOI
- [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]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]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]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]A. K. Kelmans, Cubic bipartite cyclic 4-connected graphs without Hamiltonian circuits, Russian Mathematical Surveys 43(3) (1988), 205–206.DOI
- [14]R. Sousselier, Problème no. 29: Le cercle des irascibles, Revue Française de Recherche Opérationnelle 7 (1963), 405–406.
- [15]C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Mathematics 9 (1974), 91–96.DOI
- [16]C. Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Mathematics 14 (1976), 377–389.DOI
- [17]C. Thomassen, Planar cubic hypohamiltonian and hypotraceable graphs, Journal of Combinatorial Theory, Series B 30 (1981), 36–44.DOI
- [18]W. T. Tutte, On the 2-factors of bicubic graphs, Discrete Mathematics 1 (1971), 203–208.DOI
- [19]G. Wiener, New constructions of hypohamiltonian and hypotraceable graphs, Journal of Graph Theory 87 (2018), 526–535.DOI
- [20]G. Wiener, M. Yokota and C. T. Zamfirescu, Spiders everywhere, Discrete Applied Mathematics 289 (2021), 516–522.DOI
- [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


