Another proof of the result on rotation compatible planar covers
Shohei Koizumi, Yusuke Suzuki and Kensuke Tamura · 2026
Read Another proof of the result on rotation compatible planar covers by Shohei Koizumi, Yusuke Suzuki and Kensuke Tamura (2026) 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-2606-27703.txt.
Introduction
Negami's Planar Cover Conjecture links two graph properties. A connected graph has a finite planar cover exactly when it embeds on the projective plane. The conjecture is already proved for rotation compatible planar covers. Those are covers carrying an extra condition on their rotation systems. The existing proof leans on advanced algebraic and topological methods. Shohei Koizumi, Yusuke Suzuki, and Kensuke Tamura offer another proof in 2026.
Their route is primarily combinatorial. It rests on a structural analysis built around a spanning tree of the base graph. A spanning tree reaches every vertex without cycles. Working from that skeleton, the authors rebuild the argument step by step. The new proof avoids the heavy machinery of the earlier one. It therefore makes the rotation compatible case accessible through elementary graph structure. The result itself is unchanged. What changes is the path by which readers can verify it.
Catalog record
| CREATOR | Shohei Koizumi, Yusuke Suzuki and Kensuke Tamura |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.27703
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Another proof of the result on rotation compatible planar covers Shohei Koizumi, Yusuke Suzuki and Kensuke Tamura Abstract Negami’s Planar Cover Conjecture asserts that a connected graph has a finite planar cover if and only if it can be embedded on the projective plane. While this statement has already been proven for rotation compatible planar covers, namely covers equipped with a certain condition on the rotation system, the existing proof relies on advanced algebraic and topological methods. In this paper, we provide another proof of this result, focusing primarily on combinatorial arguments based on a structural analysis with respect to a spanning tree in the base graph. Keywords: Planar Cover Conjecture, rotation compatibility, projective plane 1 Introduction In this paper, we consider only finite simple graphs. We denote the vertex set and edge set of a graph G by V(G) and E(G) , respectively. For a vertex v of a graph G , the neighborhood of v is denoted by N_{G}(v) , or simply N(v) if the graph is clear from the context. For a S\subset V(G) , we denote the subgraph induced by S by G[S] . For terminology not described here, we follow the standard graph theory terminology (e.g., see [ 4 ] ). Let \tilde{G} and G be graphs. If there exists an ( n -to-one) surjection p\colon V(\tilde{G})\to V(G) such that for any vertex \tilde{v}\in V(\tilde{G}) the restriction p|_{N(\tilde{v})}\colon N_{\tilde{G}}(\tilde{v})\to N_{G}(p(\tilde{v})) is a bijection, then \tilde{G} is an ( n - fold ) cover of G . Then, p is called a covering map (or cover projection ) of the cover, and we also write p\colon\tilde{G}\to G for such a covering map. Let L=(v_{1},\ldots,v_{k}) be a list (or a cyclic order) of vertices of \tilde{G} . We define p(L) to be the list (or cyclic order) (p(v_{1}),\ldots,p(v_{k})) ; note that vertices may appear more than once in this list. The following is the well-known Planar Cover Conjecture , proposed in 1986. C ONJECTURE 1 (Negami [ 10 ] ) A connected graph has a finite planar cover if and only if it can be embedded on the projective plane. In the conjecture above, the sufficiency is clear, but the necessity is still open. Unlike the conventional scheme which primarily focuses on showing that K_{1,2,2,2} has no finite planar cover (see e.g., [ 1 , 2 , 3 , 5 , 6 , 7 , 8 , 9 ] ), in 2024, Negami published a paper [ 11 ] presenting a new approach to Conjecture 1 , which focuses on the “rotation system” on vertices as follows. Let G be a graph embedded on an orientable closed surface F^{2} , and we fix the clockwise orientation of F^{2} . For each vertex v of G , the clockwise orientation induces a cyclic order on N(v) . We call the cyclic order above a rotation of v , and denote it by \sigma_{v} . Then \sigma_{v} can be regarded as a map \sigma_{v}\colon N(v)\to N(v) that sends each vertex u\in N(v) to its successor around v with respect to the clockwise orientation. Then \sigma_{v}^{-1} is the cyclic order on N(v) defined by the anticlockwise orientation around v ; that is, the inverse of \sigma_{v} . The rotation system \sigma is defined as \sigma=\{\sigma_{v}\colon v\in V(G)\} . Let G be a connected graph and let \tilde{G} be a cover of G with a covering map p\colon\tilde{G}\to G . Assume that \tilde{G} is embedded on an orientable closed surface F^{2} , and has a rotation system \sigma according to the clockwise orientation of F^{2} . Negami [ 11 ] proposed the following two assumptions given to the composite structure (\tilde{G},\sigma) . In fact, (\tilde{G},\sigma) is rotation compatible if (\tilde{G},\sigma) satisfies those two assumptions. Assumption 1: For any two vertices v_{1} and v_{2} of \tilde{G} such that p(v_{1})=p(v_{2}) , either p(\sigma_{v_{1}})=p(\sigma_{v_{2}}) or p(\sigma_{v_{1}})=p(\sigma^{-1}_{v_{2}}) holds. Under this assumption, the pre-images of v can be classified into two groups as follows. Assume that V(G)=\{v_{1},\ldots,v_{h}\} and V(\tilde{G})=V_{1}\cup\cdots\cup V_{h} such that v\in V_{i} if and only if p(v)=v_{i} for i\in\{1,\ldots,h\} . Then, a rotation-preserving coloring c\colon V(\tilde{G})\to\{\mbox{black},\mbox{white}\} is defined as follows. First, for each i\in\{1,\ldots,h\} , we fix a vertex v\in V_{i} , and color v in black. For any other vertex u of V_{i} , we define that u is colored in black if and only if p(\sigma_{v})=p(\sigma_{u}) ; note that if p(\sigma_{v})=p(\sigma^{-1}_{u}) , then c(u) is white. Then, we decompose V(\tilde{G}) into B\cup W , where B (resp. W ) stands for the set of black (resp. white) colored vetices of V(\tilde{G}) . For a rotation-preserving coloring c of \tilde{G} , an edge e=uv is synchronous if c(u)=c(v) , and anti-synchronous otherwise. Note further that this classification of edges also depends on c . Assumption 2: For each edge uv\in E(G) , either every element of p^{-1}(uv) is synchronous or every element of p^{-1}(uv) is anti-synchronous. As mentioned above, there are generally several rotation-preserving colorings on \tilde{G} . For a fixed i\in\{1,\ldots,h\} , exchanging the black and white colors assigned to V_{i}\subset V(\tilde{G}) switches the status of any edge between V_{i} and V_{j} (i\neq j) from synchronous to anti-synchronous, and vice versa. However, the rotation compatibility of (\tilde{G},\sigma) remains unchanged. That is, this property does not depend on the choice of rotation-preserving coloring. Negami showed the following theorem for rotation compatible covers. T HEOREM 2 (Negami [ 11 ] ) A connected graph G has a finite planar cover which is rotation compatible if and only if G can be embedded on the projective plane. By Theorem 2 , if every connected graph that admits a finite planar cover also has a finite rotation-compatible cover, then the Planar Cover Conjecture is solved. This approach, as noted above, differs from the conventional scheme, which primarily focuses on showing that K_{1,2,2,2} has no finite planar cover. The proof of Theorem 2 in [ 11 ] relies on advanced algebraic and topological methods. In this paper, we provide another simple proof based on combinatorial arguments, which will be presented in the next section. 2 Another simple proof of Theorem 2 Let G be a connected graph and let p\colon\tilde{G}\to G be its n -fold cover. Assume that \tilde{G} is embedded on the plane and is rotation compatible. Let T be a spanning tree of G , which we call a fixed spanning tree in our argument. Then \tilde{G} contains n disjoint trees T_{1},T_{2},\dots,T_{n} as subgraphs, each of which projects to T by the covering map p ; we put \mathcal{T}=\{T_{1},T_{2},\dots,T_{n}\} . Next, we consider the rotation-preserving coloring of \tilde{G} with respect to the fixed tree T , denoted by c_{T} , such that each vertex of T_{1} receives black by c_{T} . Then, for each i\in\{2,3,\dots,n\} , vertices of T_{i} are assigned the same color (either black or white) by Assumption 2; that is, every tree in \mathcal{T} is monochromatic by c_{T} . Therefore, we have the decomposition \mathcal{T}=\mathcal{T}_{B}\cup\mathcal{T}_{W} , such that \mathcal{T}_{B} (resp. \mathcal{T}_{W} ) denotes the set of black colored (resp. white colored) trees by c_{T} . For each T_{i}\in\mathcal{T} , we regard the induced subgraph \tilde{G}[V(T_{i})] as a subembedding of \tilde{G} ; that is, it is equipped with the embedding inherited from \tilde{G}