gpt 6 astra ultra attempt on Math-1082

The Berge-Fulkerson conjecture

Definitions and mathematical statement

Let $G=(V,E)$ be a finite undirected loopless cubic multigraph. Distinct parallel edges are retained, and every vertex has degree three counting multiplicities. Assume that $G$ is bridgeless, meaning that deleting any edge does not increase its number of connected components. A perfect matching is an edge set incident with every vertex exactly once; in particular no two selected edges have a common endpoint.

The Berge--Fulkerson conjecture asserts that for every such $G$ there is a list of six perfect matchings $M_1,\ldots,M_6$ satisfying \[ \sum_{i=1}^6\mathbf1_{\{e\in M_i\}}=2 \qquad\text{for every }e\in E. \] The matchings in the list are not required to be distinct. Their overlaps are permitted and indeed must achieve exactly the displayed multiplicity on every edge.

Since $G$ is cubic, a perfect matching has $|V|/2$ edges and $|E|=3|V|/2$. Thus the total edge appearances in six perfect matchings equal $3|V|=2|E|$, as required, but this counting identity alone does not ensure uniform coverage. The conjecture requests that the matchings be coordinated to give multiplicity exactly two, rather than merely having union $E$.

When three perfect matchings partition $E$, repeating each twice supplies the required list. This explains the repetition convention and the role of the conjecture as an extension of that special colouring situation.

Short English statement

Can six perfect matchings, allowing repeats, cover every edge of every bridgeless cubic graph exactly twice?

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.

Literature and approach.

The Garden formulation [S2] permits repeated perfect matchings, which is essential for the first construction below. A checked July 2026 research preprint [S3] discusses Berge--Fulkerson and related matching conjectures; it does not provide the finite general assertion used as our target. We first prove the bipartite case, then give a six-matching certificate on the Petersen graph. The latter checks that the proposed cover mechanism is not restricted to bipartite graphs.

Cubic bipartite multigraphs.

Let $G$ be cubic with bipartition $(A,B)$, allowing parallel edges but no loops. For $S\subseteq A$, exactly $3|S|$ incident edges run to $N(S)$, and the vertices of $N(S)$ receive at most $3|N(S)|$ of them. Hence $|S|\le |N(S)|$. Hall's condition gives a matching saturating $A$. Counting all edges gives $3|A|=3|B|$, so it is a perfect matching $M_1$.

Every vertex has degree two in $G-M_1$. Its components are even cycles, where a pair of parallel edges is allowed as a cycle of length two. Alternating the edges of every component produces two more perfect matchings $M_2,M_3$. Thus $M_1,M_2,M_3$ partition all edges. The six indexed matchings \[ (M_1,M_1,M_2,M_2,M_3,M_3) \] cover each edge exactly twice, as required. Nothing in the argument depends on connectedness. It also proves the target for any cubic graph supplied with a proper three-edge-colouring, by taking its three colour classes and repeating them.

An explicit nonbipartite certificate.

Present the Petersen graph by outer vertices $a_i$, inner vertices $b_i$, and edges \[ a_i a_{i+1},\qquad a_i b_i,\qquad b_i b_{i+2},\qquad i\in\mathbb Z/5\mathbb Z. \] Define $M_\infty=\{a_i b_i:i\in\mathbb Z/5\mathbb Z\}$. For each $i$, define \[ M_i=\{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}\}. \] Each displayed pair is an edge of the specified graph. In $M_i$, the spoke covers $a_i,b_i$, the two outer edges cover the other four outer vertices, and the two inner edges cover the other four inner vertices. Thus all six listed sets are perfect matchings.

A spoke $a_i b_i$ occurs precisely in $M_\infty$ and $M_i$. The five rotations $M_0,\ldots,M_4$ contain ten outer-edge occurrences altogether and act transitively on the five outer edges. Each outer edge therefore occurs twice. The same count applies to the five inner edges. No outer or inner edge belongs to $M_\infty$, so this proves the required double coverage for every edge. The graph is nonbipartite because the outer vertices form a five-cycle.

Parity checks and why this does not generalize automatically.

For any perfect matching $M$ and any vertex subset $X$, \[ |X|=2|M\cap E(G[X])|+|M\cap\delta(X)|. \tag{1} \] An odd cut in a cubic graph has odd $|X|$, since $3|X|=2|E(G[X])|+|\delta(X)|$. Thus every perfect matching meets every odd cut. In a putative sixfold cover, summing these intersections over a cut gives exactly $2|\delta(X)|$. For a three-edge cut this total is six; all six summands are positive odd integers, so each matching must meet that cut in exactly one edge. This is a stringent compatibility condition that an arbitrary selection of six matchings need not satisfy.

The script scripts/check_attempt_batch02_graphs_2026_10_01.py builds the Petersen graph, checks all six matching certificates, and checks multiplicity two on its fifteen distinct edges. These are finite checks, not sampling evidence for the unrestricted conjecture. The bipartite proof fails outside its hypothesis because a complementary 2-factor can have odd cycles, which cannot be split into two alternating matchings.

First remaining gap and final status.

We have proved the cubic bipartite case and a concrete nonbipartite instance, and identified a necessary condition on every three-edge cut. No construction here chooses six mutually compatible perfect matchings in an arbitrary bridgeless cubic multigraph. The catalogue target remains UNRESOLVED by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3179 (OPG-142), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, The Berge-Fulkerson conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/the_berge_fulkerson_conjecture.
• S3 Paulo Magalhães Júnior and Antonio Kelson Silva, On some perfect matching conjectures in infinite, cubic, bridgeless graphs, arXiv:2607.29511 $2026$. Checked for matching-conjecture context, not used as a proof of the finite target. https://arxiv.org/abs/2607.29511.