Every 2-connected, cubic, planar graph with faces of size at most 6 is Hamiltonian
Sihong Shao, Yuxuan Wu · 2025
Read Every 2-connected, cubic, planar graph with faces of size at most 6 is Hamiltonian by Sihong Shao, Yuxuan Wu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20706.txt.
Introduction
Sihong Shao and Yuxuan Wu settle a case of a long-running conjecture about cycles that visit every vertex of a network exactly once. Their 2025 paper proves that every planar graph that is two-connected, where every vertex has degree three, and whose faces have at most six sides, contains such a Hamiltonian cycle. A two-connected graph has no single vertex whose removal splits it, and the graphs are drawn flat with polygonal faces.
The bound on face size cannot be loosened: six is tight, and the authors show why. The result also weakens the connectivity demanded by the Barnette-Goodey conjecture, a classic open problem about cycles in three-regular planar graphs, pushing it to the least that can be asked. The paper is a short, sharp step in structural graph theory.
Catalog record
| CREATOR | Sihong Shao, Yuxuan Wu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-20706
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Every 2-connected, cubic, planar graph with faces of size at most 6 is Hamiltonian Sihong Shao, Yuxuan Wu Abstract Abstract : We prove that every 2-connected, cubic, planar graph with faces of size at most 6 is Hamiltonian, and show that the 6-face condition is tight. Our results push the connectivity condition of the Barnette-Goodey conjecture to the weakest possible. Keywords: Barnette’s conjecture, planar graphs, Hamiltonian cycle 1 Introduction Barnette’s conjecture states that every 3-connected, planar, cubic, bipartite graph is Hamiltonian and has stood for decades without being proved or disproved. The Barnette-Goodey conjecture, a different and possibly weaker version of Barnette’s conjecture, has been proved with computer assistance recently [ 1 ] and replaces the bipartite condition with a face condition, namely every face should be of size at most 6. The main result of this work pushes the connectivity condition of the Barnette-Goodey conjecture to the weakest possible in view of the fact that every Hamiltonian cycle is 2-connected. Theorem 1 . Every 2-connected, planar, cubic graph with faces of size at most 6 is Hamiltonian. Meanwhile, Figure 1 presents a 2-connected, planar, non-Hamiltonian, cubic graph with faces of size at most 7, thereby implying that the 6-face condition of Theorem 1 is tight. Figure 1 : The 6-face condition of Theorem 1 is tight: An example. The larger Graph G in the left is a 2-connected, planar, non-Hamiltonian, cubic graph with faces of size at most 7. To see G is indeed non-Hamiltonian, it suffices to use the fact that every Hamiltonian cycle passing through the structure in the right must use the edge e . If G is Hamiltonian, then its Hamiltonian cycle must use the edges 1 , 2 , and 3 in the left plot, which results in a contradiction. The significance and motivation of this work can be explained as follows. For Barnette’s conjecture, every possible way of weakening the condition imposed on the graph, e.g., replacing 3-connectivity with 2-connectivity, or removing the planarity or bipartite condition, renders the conjecture false, and all the decision problems of Hamiltonicity of graphs with the weaker conditions turn out to be NP-complete [ 2 , 3 ] . That is, if Barnette’s conjecture had been true, then each condition imposed on the graph would be extremely tight. Along a similar research line for the Barnette-Goodey conjecture, although it has already been proved true, it is natural and still meaningful to explore to which extent the imposed condition can be weakened. This work can be regarded as a first attempt in this line. Obviously, there are more directions worth exploring remaining open. For example, whether the Barnette-Goodey conjecture can be strengthened in the face condition, or whether Theorem 1 can possibly be further strengthened by replacing the planarity condition with something weaker. We use standard notations on graphs throughout the paper. All graphs considered in this paper are simple, undirected and finite. The rest of the paper is organized as follows. Section 2 provides several lemmas for proving Theorem 1 and Section 3 gives the proof. 2 Preliminaries and lemmas Let G=(V(G),E(G)) be a graph. For two non-intersecting subsets of V(G) , V_{1},V_{2}\subseteq V(G),V_{1}\bigcap V_{2}=\emptyset , and an edge subset S\subseteq E(G) , we let G\backslash S=(V(G),E(G)\backslash S) and E(V_{1},V_{2}) collect all edges having one endpoint in V_{1} , and the other in V_{2} . For convenience, we use G-V_{1} to denote the induced subgraph G[V\backslash V_{1}] . Below we list some facts and lemmas used in proving Theorem 1 . Proposition 2 . (Proposition 2.31 of [ 5 ] ) Let G be a 2-connected graph with a planar embedding \Phi . Then every face is bounded by a circuit, and every edge is on the boundary of exactly two faces. Moreover, the number of faces is |E(G)|-|V(G)|+2 . Corollary 3 . For a 2-connected graph G with a planar embedding \Phi , if a vertex x of G has degree 3, and e_{1},e_{2},e_{3} are the three edges x is incident with, then the three pairs of edges (e_{1},e_{2}),(e_{2},e_{3}),(e_{3},e_{1}) determine three different faces. Proof. Figure 2 : The proof of Corollary 3 . The edge e_{1} is on the boundary of two different faces F_{1},F_{2} , bounded by different circuits that go through x (see Figure 2 ). Since x has degree 3, we may assume that e_{1},e_{2} is on the boundary of F_{1} , and e_{1},e_{3} is on the boundary of F_{2} . With the same argument, e_{2} is on the boundary of two different faces F_{3},F_{4} , with F_{3} having e_{3},e_{2} on its boundary, and F_{4} having e_{2},e_{1} on its boundary. And x can be incident with at most 3 different faces since its degree is 3 . Thus F_{1}=F_{4} and the result follows. ∎ Given a 2-connected planar graph G and a planar embedding \Phi , we know that there is only one face of \Phi that extends to infinity (or equivalently, is unbounded in \mathbb{R}^{2} ). We call the unbounded face the outer face of \Phi . For the 3-dimensional sphere \mathbb{S}_{3} and a point p on it, we know there is a standard continuous bijective projection f_{p}:\mathbb{S}_{3}\backslash\{p\}\mapsto\mathbb{R}^{2} . Therefore f_{p}^{-1}\circ\Phi is an embedding onto \mathbb{S}_{3} , faces of which are in one-to-one correspondence with faces of \Phi (in the sense that the boundary cycles of the corresponding faces are the same), and the pole p in the outer face of \Phi (its counterpart in \mathbb{S}_{3} , to be precise). For any face F of \Phi , and its counterpart f_{p}^{-1}(F) of f_{p}^{-1}\circ\Phi , we can pick a point q in f_{p}^{-1}(F) , and use f_{q} to project the sphere back to the plane to get another planar embedding f_{q}\circ f_{p}^{-1}\circ\Phi , the outer face of which is F . Therefore we have the following: Proposition 4 . Given a 2-connected planar graph G and a planar embedding \Phi , for any face F of \Phi , there exists a planar embedding \Phi^{\prime} of G such that the faces of \Phi are in one-to-one correspondence with faces of \Phi^{\prime} (in the sense that the boundary cycles of the corresponding faces are the same), and F is the outer face of \Phi^{\prime} . By Proposition 4 , when considering a 2-connected planar graph G and an embedding \Phi , we can designate a face F of \Phi to be the outer face for one time. This is actually a slight abuse of notation. Hereafter when we consider a planar graph G , it is always assumed that G is accompanied with a planar embedding \Phi . Proposition 5 . Let G be a 2-connected planar graph. Suppose C is a cycle in G and V_{1} collects the vertices in the exterior of C ( C excluded). Then the induced graph H_{1}=G-V_{1} is a 2-connected planar graph, too. Proof. Obviously H_{1} is planar and connected. \forall x\in V(H_{1}) , we are going to prove H_{1}-\{x\} is connected. That is, we need to find a walk connecting y and z for all vertex pairs of y,z\in H_{1}-\{x\},y\neq z . Since G is 2-connected, there is a walk P connecting y,z in G-\{x\} . If P is contained in the interior of C ( C included),