TOPICS
Search

Planar Hypotraceable Graph


PlanarHypotraceableGraphs

A planar hypotraceable graph is a hypotraceable graph that is also planar. A number of planar hypotraceable graphs are illustrated above.

Using a theorem of Thomassen (1974), the Wiener-Araya graph on 42 vertices can be used to construct a planar hypotraceable graph on 162 vertices, smaller than the 186-vertex graph obtained from the 48-Zamfirescu graph using Thomassen's construction.

Jooyandeh et al. (2017) showed that there exist planar hypotraceable graphs on 154 vertices, as well as on all vertex counts greater than or equal to 156.

Tsai (2025) constructed an example on 130 vertices. Durias et al. (2026) established existence for every order n>=132. Fixing the 34-vertex graph G_7 of Tsai (2025), the four-copy construction gives 39 pairwise non-isomorphic results when the same graph vertex of degree 3 is deleted and all three neighbors have the same attachment roles in every copy, including the neighbor chosen for vertex identification. Allowing the deleted vertices, the identified neighbors, and the assignments of the other two neighbors to vary independently between copies gives 2,316,483 pairwise non-isomorphic planar hypotraceable graphs on 130 vertices.

Using the 70-node Araya-Wiener graph, a 340-node cubic planar hypotraceable graph can be constructed (Araya and Wiener 2011). For five copies of this particular Araya-Wiener graph, there are 53 pairwise non-isomorphic results when the endpoints of the same graph edge are deleted and the same attachment roles are used in every copy. Allowing the deleted edges and attachment roles to vary independently, while retaining planarity, gives 20,420,527,092 pairwise non-isomorphic cubic planar hypotraceable graphs on 340 vertices.

In the four-copy construction used by Tsai (2025), any graph vertex of degree 3 may be deleted in each copy, and any of its neighbors may be chosen for vertex identification. In the five-copy construction used by Araya and Wiener (2011), the endpoints of any graph edge may be deleted in each copy, with attachment roles chosen to preserve planarity.

Holton and Sheehan (1993) asked if there exists an integer n such that a cubic planar hypotraceable graph exists for every even integer >=n, and Araya and Wiener (2011) settled the question with n=356.

The illustrated planar hypotraceable graphs on n=130, 162, 186, and 340 vertices will be available in a future version of the Wolfram Language as GraphData[{"PlanarHypotraceable", n}].


See also

Hamilton-Connected Graph, Hypotraceable Graph, Planar Graph, Planar Hypohamiltonian Graph, Thomassen Graphs, Traceable Graph, Wiener-Araya Graph, Zamfirescu Graphs

Explore with Wolfram|Alpha

References

Araya, M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs." Elec. J. Combin. 18, No. 1, P85, 2011. https://doi.org/10.37236/572.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 61 and 239-240, 1976.Durias, S.; Guerrero, S.; Jaiyen, B.; Kaplan, D.; Lapine, A.; Peralta, C.; and Shrivastav, A. "Local Modifications in Planar Hypohamiltonian Graphs." 15 Oct 2026. https://arxiv.org/abs/2610.21210.Grotschel, M. "On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets." Math. Operations Res. 5, 285-292, 1980.Grünbaum, B. "Vertices Missed by Longest Paths or Circuits." J. Combin. Th. A 17, 31-38, 1974.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Jooyandeh, M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.; and Zamfirescu, C. T. "Planar Hypohamiltonian Graphs on 40 Vertices." J. Graph Th. 84, 121-133, 2017.Kapoor, S. F.; Kronk, H. V.; and Lick, D. R. "On Detours in Graphs." Canad. Math. Bull. 11, 195-201, 1968.Thomassen, C. "Hypohamiltonian and Hypotraceable Graphs." Disc. Math. 9, 91-96, 1974.Tsai, C.-C. "Small Planar Hypohamiltonian Graphs." J. Graph Th. 108, 799-807, 2025. https://doi.org/10.1002/jgt.23205.Walter, H. "Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen." J. Combin. Th. 6, 1-6, 1969.Wiener, G. and Araya, M. "The Ultimate Question." 20 Apr 2009. https://arxiv.org/abs/0904.3012.Wiener, G. and Araya, M. "On Planar Hypotraceable Graphs." J. Graph Th. 67, 55-68, 2011.

Referenced on Wolfram|Alpha

Planar Hypotraceable Graph

Cite this as:

Weisstein, Eric W. "Planar Hypotraceable Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PlanarHypotraceableGraph.html

Subject classifications