gpt 6 astra ultra attempt on Math-1091

Petersen coloring conjecture

Definitions and mathematical statement

Define the Petersen graph $P$ as the graph whose vertices are the two-element subsets of $\{1,2,3,4,5\}$, with two vertices adjacent exactly when the subsets are disjoint. It has ten vertices, each of degree three. For any loopless graph $H$ and vertex $v$, let $\delta_H(v)$ denote its set of incident edges.

Let $G$ be a finite loopless cubic multigraph with no bridge. A Petersen colouring of $G$ is a function $f:E(G)\to E(P)$ satisfying \[ \forall v\in V(G)\quad\exists w\in V(P): \quad f\big|_{\delta_G(v)}: \delta_G(v)\longrightarrow\delta_P(w) \text{ is a bijection}. \] In particular, the three distinct edges at each vertex of $G$ receive three distinct Petersen-edge labels forming one complete star of $P$. The same label may be used at unrelated locations in $G$.

The conjecture asserts that every bridgeless cubic $G$ admits such a map. The function colours edges, not vertices; it is not required to be an isomorphism, a covering map, or surjective onto all fifteen edges of $P$. The chosen vertex $w$ may depend on $v$. The local star formulation makes the meaning of the source's mutually adjacent edge triples precise. Since the Petersen graph is triangle-free, three distinct pairwise adjacent edges there necessarily form a star. Every adjacent pair of source edges receives distinct incident labels by the displayed condition.

Short English statement

Can the edges of every bridgeless cubic graph be labelled by Petersen-graph edges so each vertex sees exactly the three edges at some Petersen vertex?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 1 October 2026. The catalogue formulation is retained above. This attempt checks the original problem and primary literature, proves the restricted claims stated below, and identifies the exact limit of its conclusions. Reproved facts are not claimed as novel results.

Current literature and scope of the audit.

The historical Garden conjecture has a material update. Goedgebeur, Jooken, Máčajová, Mattiolo, Mazzuoccolo and Ulyanov [S4], version 4 dated 30 September 2026, report theoretical counterexamples on fifty-two vertices and an infinite family at every even order at least sixty. We do not portray the universal catalogue statement as still open in the face of that source. This attempt independently checks local consequences of a Petersen colouring and an affirmative subclass; it does not rederive the paper's multipole counterexample proof.

The local star condition is exact.

Three distinct pairwise incident edges of a simple graph either have one common endpoint or form a triangle. To see this, name two edges $xy,xz$. A third meeting both either uses $x$, or must be $yz$. The Petersen graph is triangle-free, so a triple of mutually incident distinct target edges forms a complete star at a target vertex. Thus the adjacent-edge formulation and the catalogue's bijection onto a star agree for a cubic source. Distinctness matters: assigning one label to several incident edges is not a Petersen colouring.

A complete affirmative subclass.

If a cubic graph $G$ has a proper edge-colouring with three colours, fix any Petersen vertex $w$ and label the three colours by the three distinct edges incident to $w$. Every source vertex sees all three colours, so this map satisfies the star condition. It need not be surjective onto the fifteen target edges; using three of them is sufficient.

In particular, every cubic bipartite multigraph admits such a map. For a bipartition $(A,B)$, counting incident edges gives $|N(X)|\ge|X|$ for each $X\subseteq A$, since $3|X|\le3|N(X)|$. Hall's theorem supplies a perfect matching, and $|A|=|B|$ by cubic degree summation. Removing the matching leaves even cycles, including possible two-edge parallel cycles. Alternating two further colours on them gives a proper three-edge-colouring. This verifies all the local constraints even for the multigraph convention in the definition.

Pulling back matchings and even subgraphs.

Let $f:E(G)\to E(P)$ be a Petersen colouring and $N$ any perfect matching of $P$. At the star associated with each source vertex, exactly one target edge lies in $N$. Therefore exactly one source edge incident with that vertex belongs to $f^{-1}(N)$. This proves that $f^{-1}(N)$ is a perfect matching of $G$, regardless of repeated labels at distant edges.

More generally, if $Z\subseteq E(P)$ has even degree at every target vertex, then its local degrees are zero or two because $P$ is cubic. The star bijections imply that $f^{-1}(Z)$ has degrees zero or two at every source vertex. It is a disjoint union of cycles and isolated vertices, not necessarily a single connected cycle. Requiring connectedness of this preimage would be an unjustified strengthening.

For a concrete consequence, present $P$ with outer edges $a_i a_{i+1}$, spokes $a_i b_i$ and inner edges $b_i b_{i+2}$, with indices modulo five. Its spoke matching and the five matchings \[ \{a_i b_i,a_{i+1}a_{i+2},a_{i+3}a_{i+4}, b_{i+2}b_{i+4},b_{i+1}b_{i+3}\} \] cover every edge twice. Each displayed set is perfect by inspection; spokes occur in exactly two sets, and rotational symmetry distributes the ten outer and ten inner occurrences twice per edge. Pulling these six matchings back along $f$ yields a Berge--Fulkerson double cover of $G$. Thus that cover is a necessary consequence of a Petersen colouring. A reported graph without a Petersen colouring does not, by this one-way implication, disprove Berge--Fulkerson.

A misleading covering-map shortcut.

Apply the three-colour construction to $K_4$, using its three disjoint perfect-matching colour classes. Every source star maps to the same star at $w$. There cannot be a compatible vertex covering map sending all source vertices to $w$, since an edge would then have equal target endpoints in a loopless graph. This explicit example shows why a Petersen edge-colouring is not a topological graph covering, despite its local star bijections. Covering-space arguments imposing that extra structure can miss valid colourings.

The script scripts/check_attempt_batch02_graphs_2026_10_01.py checks the $K_4$ labelling, the six Petersen matchings, and their pullback multiplicities. The all-graph pullback claims are proved above independently of this finite test.

Final status.

The affirmative subclass and pullback lemmas are proved. The universal conjecture is reported disproved in [S4]. Independent reproduction of that disproof is UNRESOLVED in this attempt; specifically, no fifty-two-vertex obstruction is independently certified here. The positive local results do not override the current counterexample literature.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3196 (OPG-143), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Petersen coloring conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/petersen_coloring_conjecture.
• S3 F. Pirot, J.-S. Sereni and R. Škrekovski, Variations on the Petersen colouring conjecture, Electronic Journal of Combinatorics 27 $2020$, P1.8; edge-map interpretation. https://arxiv.org/abs/1905.07913.
• S4 Jan Goedgebeur, Jorik Jooken, Edita Máčajová, Davide Mattiolo, Giuseppe Mazzuoccolo and Nikolay Ulyanov, Disproving the Petersen Coloring Conjecture: Theoretical Analysis and an Infinite Family of Counterexamples, arXiv:2608.10028v4, revised 30 September 2026. Primary reported disproof; its multipole proof is not independently reproduced here. https://arxiv.org/html/2608.10028v4.