GPT 6 Astra Ultra attempt on Math-1094

Pentagon problem

Definitions and mathematical statement

Let $G$ be a finite simple cubic graph, so each vertex has exactly three neighbours. Its girth is the length of its shortest simple cycle. Let $C_5$ be the cycle with vertex set $\mathbb Z/5\mathbb Z$, where two residues are adjacent when their difference is $1$ or $-1$. A homomorphism $f:G\to C_5$ is a vertex map preserving adjacency, equivalently a function satisfying \[ f(v)-f(u)\equiv 1\text{ or }-1\pmod5 \qquad(uv\in E(G)). \] The map need not be injective or surjective.

The Pentagon Problem asks whether there exists an absolute integer $g_0$ such that every finite simple cubic graph with girth at least $g_0$ has a homomorphism to $C_5$. The threshold is chosen once and must work for all graph orders and all cubic graphs above it; it cannot depend on $G$.

The target demands more than an ordinary proper colouring with five colours. Only consecutive colours around the fixed pentagon may appear at the ends of an edge. Equivalently, the vertices are partitioned into five possibly empty classes, each independent, with edges permitted only between consecutive classes cyclically. The hypothesis forbids all short cycles, not only short odd cycles. A negative answer would be a family of cubic graphs of unbounded girth admitting no pentagon homomorphism. Disconnected graphs are allowed and can be mapped component by component using the same target.

Short English statement

Does one sufficiently large girth threshold guarantee that every cubic graph admits an adjacency-preserving map to a pentagon?

Research attempt

Scope and method.

This research attempt by GPT-6 Astra Ultra is dated 1 October 2026. It preserves the catalogue statement and distinguishes elementary proofs below from cited prior work. No novelty claim or formal proof-assistant verification is made. The final paragraph states the precise remaining scope.

Literature boundary.

The problem is attributed to Nešetřil in [S2]. DeVos and Šámal [R1] prove that cubic graphs of girth at least seventeen map to the Clebsch graph. Their target is not $C_5$, and their cut-continuous edge mapping must not be confused with the vertex homomorphism required here. We investigate the exact consistency equations for a $C_5$ mapping.

A cycle-space formulation.

Orient every edge arbitrarily. A homomorphism is a potential $x:V\to\mathbb Z/5\mathbb Z$ whose difference on each oriented edge belongs to $\{1,-1\}$. Thus it assigns a sign $\epsilon_e$ to every edge, and on every cycle the signed sum, using traversal direction, is zero modulo five. These conditions are also sufficient. Choose a root in each component, set its potential to zero, and integrate the signs along a spanning tree. For a non-tree edge the fundamental-cycle equation gives the required potential difference. Consequently it suffices to impose one equation for each non-tree edge, rather than enumerate all cycles. This is an exact reduction, but the unknown signs occur simultaneously in several equations and cannot be chosen separately for each cycle.

Solving individual cycles.

A closed walk of length $m$ in $C_5$ exists precisely when one can choose $m$ signs with total divisible by five. Every even $m$ works by taking equal numbers of positive and negative steps. For odd $m\ge5$, take $(m+5)/2$ positive and $(m-5)/2$ negative steps, giving total five. For a triangle, the only totals are $-3,-1,1,3$, none divisible by five. It follows that every cycle of length at least four maps to $C_5$. A forest maps by its bipartition onto one fixed target edge. More generally, a cactus with no triangle maps to $C_5$: attach its edge and cycle blocks one at a time at their common cutvertex and rotate the target labels so that the attaching vertex agrees. This proves a useful compatibility case, but finite cubic graphs need not have a cactus block structure; the result is not a high-girth cubic theorem.

A necessary global inequality.

Write $V_i=x^{-1}(i)$ for a proposed mapping. For each $i$ modulo five, $V_i\cup V_{i+2}$ is independent because those target vertices are nonadjacent. Each source vertex belongs to exactly two of these five independent sets. Hence \[ 5\alpha(G)\ \ge\ \sum_{i=0}^4|V_i\cup V_{i+2}|=2|V(G)|. \] Thus $\alpha(G)\ge2|V(G)|/5$ is necessary. This counts actual preimages; it does not assume the five classes have equal size. It is not sufficient: a triangle together with enough isolated vertices satisfies the numerical inequality while still having no mapping. That example is deliberately outside the cubic high-girth hypothesis and diagnoses only the loss of information in the independence-number relaxation.

Why a factor-by-factor construction stops.

Suppose a cubic graph has a perfect matching and all cycles of its complement are long enough to map. Choose one mapping on each cycle. Rotating and reversing it gives parameters $a_C\in\mathbb Z/5\mathbb Z$ and $s_C\in\{1,-1\}$. Every matching edge $uv$ between cycles $C,D$ then demands $a_C+s_Cx(u)-a_D-s_Dx(v)\in\{1,-1\}$. Local cycle solvability supplies no theorem that this coupled constraint system is satisfiable. Moreover, restricting to rotations of one chosen cycle mapping discards other possible sign patterns, so failure of this restricted search would not disprove the conjecture.

Verification and final status.

The accompanying root batch script enumerates possible walk residues for lengths up to forty, checks the cycle criterion, and validates explicit cubic prism mappings for base cycles of length at least four. Prisms have four-cycles, so these certificates do not supply an unbounded-girth family. UNRESOLVED. The exact cycle-space reduction and the necessary independence bound are proved. A uniform argument satisfying all overlapping cycle or matching constraints at sufficiently large girth remains missing.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3207 (OPG-167), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Pentagon problem. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/pentagon_problem.
• R1 Matt DeVos and Robert Šámal, High-girth cubic graphs are homomorphic to the Clebsch graph, arXiv:math/0602580. Primary abstract checked 1 October 2026. https://arxiv.org/abs/math/0602580.