gpt 6 astra ultra attempt on Math-615

Barnette's Conjecture

Definitions and mathematical statement

All graphs in this statement are finite, simple, and undirected. A graph $G=(V,E)$ is cubic if every vertex has degree three, and bipartite if $V$ admits a partition into two sets with every edge joining different sets. It is planar if its vertices and edges can be drawn in the plane without crossings between edge interiors. It is $3$-connected if $|V|\geq4$ and removing any set of at most two vertices leaves it connected.

A Hamilton cycle is a simple cycle containing every vertex of the graph. Equivalently, for $n=|V|$, it is a cyclic ordering $v_1,\ldots,v_n$ of all vertices, without repetition, such that $v_iv_{i+1}\in E$ for each index interpreted modulo $n$.

Barnette's conjecture asserts that every graph satisfying all four properties---$3$-connected, cubic, planar, and bipartite---has a Hamilton cycle. The cycle uses exactly two of the three incident edges at every vertex. Consequently, its unused edges form a perfect matching, namely a set of edges incident with every vertex exactly once. An equivalent target is therefore to find a perfect matching whose edge complement is one connected cycle.

There is no designated planar embedding or prescribed set of edges the cycle must use. A union of several disjoint cycles covering all vertices is only a spanning $2$-regular subgraph and does not fulfil the required connectedness.

Short English statement

Does every 3-connected cubic planar bipartite graph have a cycle visiting every vertex exactly once?

Research attempt: perfect matchings and a certified face switch

Scope and literature check.

GPT-6 Astra Ultra, 1 October 2026. A spanning two-factor may have several components, so proving its existence is only the first step. Schnieders' primary preprint [S3] proves a substantially stronger restricted result for Barnette graphs with faces of size at most eight, using a large computational case analysis. That theorem is credited externally; its computation is not reproduced here. The present attempt investigates the elementary operation of merging two components across a square face and identifies the condition that prevents a straightforward induction.

1. Producing the initial two-factor.

Let $(A,B)$ be the bipartition of a cubic graph. Counting edges gives $3|A|=3|B|$. For any $X\subseteq A$, its $3|X|$ incident edges all end in $N(X)$, and each vertex of $N(X)$ receives at most three; therefore $|N(X)|\ge|X|$. This is Hall's condition for a perfect matching. For completeness, take a maximum matching. If it misses a vertex of $A$, follow alternating unmatched/matched edges from all unmatched vertices in $A$. An unmatched reachable vertex in $B$ would give an augmenting path, contradicting maximal size. Thus every reachable $B$-vertex is matched to a reachable $A$-vertex, while at least one reachable $A$-vertex is unmatched. The reachable sets then violate $|N(X)|\ge|X|$. Hence the matching is perfect.

Its complement $F$ has degree two at every vertex and so is a disjoint union of cycles. Since the graph is bipartite, all those cycles are even. Choose among all perfect matchings one whose complement has as few components as possible.

2. A square that merges two components.

Suppose a four-cycle has cyclic vertices $x,y,z,w$, with $xy,zw\in F$ and $yz,wx\in M$. Define \[ F'=F\mathbin{\triangle}\{xy,yz,zw,wx\},\qquad M'=M\mathbin{\triangle}\{xy,yz,zw,wx\}. \] At each of the four vertices, exactly one matching edge is exchanged for another, so $M'$ is again a perfect matching and $F'$ is its two-factor complement. If $xy$ and $zw$ belong to different components of $F$, removing them turns those two cycles into two paths with endpoints $x,y$ and $z,w$. Adding $yz$ and $wx$ joins the paths into one cycle. All other components are unchanged. Thus the total number of components decreases by one.

Consequently a minimum-component two-factor cannot have such an alternating square with its two selected edges in different components. This is a useful, checkable structural restriction on any hypothetical counterexample together with an optimal matching. If the two selected edges lie on the same component, the operation need not decrease the number of components, so that hypothesis cannot be omitted.

3. What planarity forces, and what it does not.

In a plane embedding of a three-connected cubic graph, every facial boundary is a simple cycle. Euler's formula and $3|V|=2|E|$ give \[ \sum_{f}(6-|\partial f|)=12. \] Every face length is even and at least four. A four-face contributes two, a six-face zero, and longer faces contribute negatively. There must therefore be at least six four-faces. However, the identity says nothing about whether a four-face alternates between $M$ and $F$, or whether its two $F$-edges lie in different components. Counting squares alone cannot certify an available merging move.

As a direct family check, the prism $C_{2m}\mathbin{\square}K_2$, $m\ge2$, has a Hamilton cycle that traverses one layer in the order $0,1,\ldots,2m-1$, crosses to the other layer, traverses that layer in reverse order, and crosses back. Both cross-edges exist and the sequence visits every vertex once. The script [S4] checks these cycles for $2\le m\le8$, and verifies a cube switch merging its two square layers into one spanning cycle.

First remaining gap.

The local move is fully justified, but no argument guarantees a mergible alternating square for an arbitrary minimum-component matching. Reconfiguring the matching without increasing the number of components might eventually expose one; termination and access to such a configuration are not proved here.

Final status

UNRESOLVED. Perfect matching existence, the merging criterion, and explicit prism certificates are established. They do not prove that every Barnette graph has a connected two-factor. Completion estimate: no defensible global percentage.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3166 (OPG-385), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Barnette's Conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/barnettes_conjecture.
• S3 T. Schnieders, Barnette Graphs with Faces up to Size 8 are Hamiltonian, arXiv:2508.03531 $2025$. Checked 1 October 2026. https://arxiv.org/abs/2508.03531.
• S4 GPT-6 Astra Ultra, exact prism and cube-switch checks, 1 October 2026: scripts/check_attempt_batch02_connectivity_2026_10_01.py in this repository; run with Python 3.