Negami's Conjecture

Negami’s Finite Planar-Cover Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A finite graph cover is a surjection $p:V(\widetilde G)\to V(G)$ that sends the neighbours of each $v\in\widetilde G$ bijectively onto the neighbours of $p(v)$. For a finite connected graph $G$, the hypothesis is that some finite covering graph $\widetilde G$ is planar. The conclusion is a crossing-free embedding of $G$ in the real projective plane. [S1] [S2]

Statement recorded in the supplied source.

Does every graph with a planar cover have a projective-plane embedding? [S1]

Scope and interpretation.

Finiteness and local bijectivity are essential parts of the planar-cover formulation recorded in the archive’s source review; an arbitrary graph homomorphism or infinite universal cover is not a substitute. [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Rule out every finite planar cover of K_{1,2,2,2}, or construct one and thereby refute the conjecture. [S1]

Short English statement

Does admitting a finite planar covering graph force a connected graph to embed in the projective plane?

Research attempt

Status: UNRESOLVED. We prove constant sheet number for finite covers of connected graphs, derive Euler obstructions, and explain the projective-plane-to-planar-cover direction. The converse cannot be obtained from the counting constraints alone.

Source and scope.

Annor--Nikolayevsky--Payne [S2], primary abstract checked 1 October 2026, rules out planar covers of $K_{1,2,2,2}$ having certain structures and restricts a possible minimal cover. It does not claim the full conjecture. Our work retains finite locally bijective covers; a general homomorphism or an infinite tree cover would change the problem.

Fibres all have the same size.

Let $p:\widetilde G\to G$ be a finite graph cover and suppose $uv$ is an edge of $G$. Each vertex over $u$ has exactly one neighbour over $v$, by local bijectivity. Each vertex over $v$ likewise has exactly one neighbour over $u$. Those lifted edges therefore define a bijection between the two fibres. Since $G$ is connected, paths propagate equality of fibre sizes to every vertex. Write the common positive size as $q$.

If $G$ has $n$ vertices and $m$ edges, it follows that \[ |V(\widetilde G)|=qn,\qquad |E(\widetilde G)|=qm. \] The edge count follows either from the $q$ lifts of each base edge or from degree preservation and the handshake identity. Connectedness of the covering graph is not needed for these total counts. Its components themselves map onto the connected base, because the lift of each base path remains in the starting component.

Euler obstructions to a planar cover.

Assume $G$ is simple and $qn\ge3$. Its locally bijective cover is also simple under the usual simple-graph convention. If the cover is planar, the planar edge inequality gives \[ qm\le3qn-6,\qquad m\le3n-\frac6q<3n. \] In particular every graph with $m\ge3n$ has no finite planar cover. There is a local version: if $G$ has minimum degree at least six, then so does its cover, contradicting the fact that every finite simple planar graph has a vertex of degree at most five.

If $G$ is triangle-free, its cover is triangle-free too. A triangle upstairs would project to a closed walk of length three without an immediate reversal; local bijectivity excludes such a reversal, and in a simple base it would be a triangle. Hence the stronger planar bound yields $qm\le2qn-4$ and $m<2n$.

These are necessary conditions, not a characterization. For the principal unresolved obstruction $K_{1,2,2,2}$, $n=7$ and $m=(7^2-(1^2+2^2+2^2+2^2))/2=18$. The ordinary Euler inequality only says $18q\le21q-6$, or $q\ge2$. Its vertices have degree six in the singleton part and degree five in the other parts, so the minimum-degree obstruction also fails. This explicitly exhibits the limit of the elementary count.

The known easy direction via the antipodal sphere.

Suppose $G$ is embedded without crossings in the real projective plane. View that surface as $S^2$ with antipodal points identified. The quotient map is a two-sheeted local homeomorphism. Lift the embedded vertices and edge arcs to $S^2$. Each base vertex has two lifts, and in a small disk around a lift the incident edges map bijectively to the incident edges downstairs. Thus the lifted graph is a finite graph cover.

Its drawing on the sphere has no crossings, because two crossing lifts would project to a crossing downstairs. Removing a point from a face and identifying the punctured sphere with the plane gives a plane drawing. This proves that projective-plane embeddability implies existence of a finite planar cover. It does not construct an embedding downstairs from an arbitrary cover, because an arbitrary graph cover need not be the restriction of a surface covering with a compatible antipodal involution.

Why infinite covers and quotients do not finish the converse.

The universal covering graph of any connected graph is a tree, obtained by unfolding non-backtracking walks from a root. Each incident base edge has a unique lifted continuation, so local bijectivity holds. Such a tree is planar but may be infinite. Thus removing finiteness would make the planar-cover condition hold for all connected graphs, including nonprojective ones. The finite Euler arguments cannot be applied to an infinite tree by simply cancelling an infinite sheet number.

Conversely, identifying vertices in a finite plane graph can create crossings in its quotient. Local bijectivity controls incidence neighborhoods, but does not say that the cyclic orders around all vertices in a fibre agree up to one consistent reversal. A proof of the conjecture would have to extract the required surface compatibility or another global structure.

Verification and remaining gap.

The identities account for every edge once at the base and exactly $q$ times upstairs. Small bases with fewer than three lifted vertices can be handled directly and are irrelevant to the obstruction calculation. No cover enumeration was run.

The exact remaining step is excluding a finite planar cover of the unresolved obstruction or proving that any permitted planar cover carries a compatible projective-plane embedding of its base. The elementary bounds only exclude dense bases and some cover degrees; they leave $K_{1,2,2,2}$ beyond the one-sheet case untouched. The full converse remains unresolved here.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1406 (GRAPH-019), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 D. Y. B. Annor, Y. Nikolayevsky, and M. S. Payne, Three Theorems on Negami's Planar Cover Conjecture, arXiv:2412.19560 $2024$. https://arxiv.org/abs/2412.19560. Bibliographic information from the supplied record.

• S3 S. Negami, Another approach to Planar Cover Conjecture focusing on rotation systems, Journal of the Mathematical Society of Japan 76 $2024$, 975–996. https://doi.org/10.2969/jmsj/90769076. Bibliographic information from the supplied record.