[#P3070] Barnette’s conjecture

A bipartite planar cubic graph with an orange cycle passing through almost every vertex. — A structural graph diagram of the statement's mathematical objects.

Problem. Does every finite simple cubic, \(3\)-connected, bipartite planar graph \(G\) contain a Hamiltonian cycle?

1Context

Known frontier: Every n-vertex Barnette graph has a subhamiltonian cycle containing at least 5n/6 edges. The conjecture has been verified through 90 vertices and proved when every face has size at most 8. Open boundary: Prove that every Barnette graph has a spanning cycle, or exhibit a cubic, 3-connected, bipartite planar graph without one. A repository corpus search for Barnette returned no duplicate target.

2Problem setup

Definition 1 (cubic). Every vertex has degree 3.

Definition 2 (3-connected). Deleting any two vertices leaves the graph connected.

Definition 3 (Hamiltonian cycle). A cycle that visits every vertex exactly once.

Remark 1. A Barnette graph is cubic, 3-connected, bipartite, and planar. The conjecture asks whether every such graph has a cycle visiting every vertex exactly once.

3What counts as a solution

Prove that every finite simple cubic, 3-connected, bipartite planar graph has a Hamiltonian cycle.
Or give an explicit graph satisfying all four hypotheses, together with a rigorous certificate that it has no Hamiltonian cycle.

1Status

Current status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: Every n-vertex Barnette graph has a subhamiltonian cycle containing at least 5n/6 edges. The conjecture has been verified through 90 vertices and proved when every face has size at most 8. Exact unresolved remainder: Prove that every Barnette graph has a spanning cycle, or exhibit a cubic, 3-connected, bipartite planar graph without one. TheoremDB corpus searches for Barnette returned no duplicate target.^[1][2][3][4]

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 OPEN as checked on 2026-08-01. Strongest checked neighboring result: Every n-vertex Barnette graph has a subhamiltonian cycle containing at least 5n/6 edges. The conjecture has been verified through 90 vertices and proved when every face has size at most 8. Exact unresolved remainder: Prove that every Barnette graph has a spanning cycle, or exhibit a cubic, 3-connected, bipartite planar graph without one. TheoremDB corpus searches for Barnette returned no duplicate target.^[1][2][3][4] Relevance to this problem This is the dated publication status for the canonical target Barnette’s conjecture. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2, Reference 3, Reference 4 Details The problem was checked as open on 2026-08-01. The strongest neighboring result found in the cited sources is: Every n-vertex Barnette graph has a subhamiltonian cycle containing at least 5n/6 edges. The conjecture has been verified through 90 vertices and proved when every face has size at most 8. The exact unresolved remainder is: Prove that every Barnette graph has a spanning cycle, or exhibit a cubic, 3-connected, bipartite planar graph without one. TheoremDB corpus searches for Barnette returned no duplicate target. A complete resolution must meet the following acceptance conditions: - Prove that every finite simple cubic, 3-connected, bipartite planar graph has a Hamiltonian cycle. - Or give an explicit graph satisfying all four hypotheses, together with a rigorous certificate that it has no Hamiltonian cycle. Open full record →
	Result	Supported
claim · Claim 2 Every n-vertex Barnette graph has a subhamiltonian cycle containing at least 5n/6 edges. The conjecture has been verified through 90 vertices and proved when every face has size at most 8.^[1][2][3][4] Relevance to this problem Locates the present research frontier immediately below Barnette’s conjecture. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2, Reference 3, Reference 4 Details Every n-vertex Barnette graph has a subhamiltonian cycle containing at least 5n/6 edges. The conjecture has been verified through 90 vertices and proved when every face has size at most 8. This leaves the following boundary unresolved: Prove that every Barnette graph has a spanning cycle, or exhibit a cubic, 3-connected, bipartite planar graph without one. TheoremDB corpus searches for Barnette returned no duplicate target. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
	Trace	Supported
attempt · Route 1 The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Every n-vertex Barnette graph has a subhamiltonian cycle containing at least 5n/6 edges. The conjecture has been verified through 90 vertices and proved when every face has size at most 8. Unresolved remainder: Prove that every Barnette graph has a spanning cycle, or exhibit a cubic, 3-connected, bipartite planar graph without one. TheoremDB corpus searches for Barnette returned no duplicate target.^[1][2][3][4] Relevance to this problem Documents why Barnette’s conjecture was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2, Reference 3, Reference 4 What happened The audit ran on 2026-08-01 across the cited primary literature and problem collections, Crossref, arXiv, and stable publisher records, TheoremDB published, prospecting, packet, formal, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - Barnette conjecture cubic bipartite planar graph Hamiltonian open - Barnette graph face size 8 Hamiltonian - Barnette graphs verified 90 vertices The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Every n-vertex Barnette graph has a subhamiltonian cycle containing at least 5n/6 edges. The conjecture has been verified through 90 vertices and proved when every face has size at most 8. Unresolved remainder: Prove that every Barnette graph has a spanning cycle, or exhibit a cubic, 3-connected, bipartite planar graph without one. TheoremDB corpus searches for Barnette returned no duplicate target. Related: Claim 1 Open full record →
	Trace	Reported
attempt · Route 2 Prove that every Barnette graph has a spanning cycle, or exhibit a cubic, 3-connected, bipartite planar graph without one. TheoremDB corpus searches for Barnette returned no duplicate target. Relevance to this problem Turns the remaining uncertainty in Barnette’s conjecture into a checkable research target. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: Prove that every Barnette graph has a spanning cycle, or exhibit a cubic, 3-connected, bipartite planar graph without one. TheoremDB corpus searches for Barnette returned no duplicate target. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - Prove that every finite simple cubic, 3-connected, bipartite planar graph has a Hamiltonian cycle. - Or give an explicit graph satisfying all four hypotheses, together with a rigorous certificate that it has no Hamiltonian cycle. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: Every n-vertex Barnette graph has a subhamiltonian cycle containing at least 5n/6 edges. The conjecture has been verified through 90 vertices and proved when every face has size at most 8. Exact unresolved remainder: Prove that every Barnette graph has a spanning cycle, or exhibit a cubic, 3-connected, bipartite planar graph without one. TheoremDB corpus searches for Barnette returned no duplicate target.

Equivalent-formulation queries: Barnette conjecture cubic bipartite planar graph Hamiltonian open; Barnette graph face size 8 Hamiltonian; Barnette graphs verified 90 vertices
Strongest checked neighboring result: Every n-vertex Barnette graph has a subhamiltonian cycle containing at least 5n/6 edges. The conjecture has been verified through 90 vertices and proved when every face has size at most 8.
Exact unresolved remainder: Prove that every Barnette graph has a spanning cycle, or exhibit a cubic, 3-connected, bipartite planar graph without one. TheoremDB corpus searches for Barnette returned no duplicate target.

How the 4 records connectTyped relations and evidence flow

ProblemBarnette’s conjecture

Claim 1Current status and exact unresolved remainderin this packetSupported
Route 1Dated source and duplicate auditchecksSupported
Claim 2Strongest checked neighboring resultinformsSupported
Route 2Work at the unresolved boundaryaddressesReported

2See also

Cycle Double Cover Conjecturecombinatorics
The Total Coloring Conjecturecombinatorics
Sabidussi's Compatibility Conjecturecombinatorics

How to cite

TheoremDB contributors, “Barnette’s conjecture,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/barnette-conjecture

This page as plain text: barnette-conjecture.md

This problem includes 4 records joined by 3 typed links, sourced from doi.org^[1], current as of August 1, 2026.

1References

Packet source. M. A. Bekos, M. Kaufmann, and M. Pfister, Approximating Barnette’s Conjecture, 33rd International Symposium on Graph Drawing and Network Visualization, LIPIcs 357, Article 6, pp. 6:1-6:7 (2025). Abstract, Introduction, Theorem 1, and Section 5. ↗ open copy ↗proceedings article · primary source · checked 2026-08-01Source use: original summary.States that the conjecture remains open and proves that every n-vertex Barnette graph has a subhamiltonian cycle containing at least 5n/6 edges.Also cited at M. A. Bekos, M. Kaufmann, and M. Pfister, Approximating Barnette’s Conjecture, 33rd International Symposium on Graph Drawing and Network Visualization, LIPIcs 357, Article 6, pp. 6:1-6:7 (2025). Abstract, Introduction, Theorem 1, and Section 5.Source used to assess the problem's recorded status.For Barnette’s conjecture: This is the dated publication status for the canonical target Barnette’s conjecture.Source named by the research packet.
Schnieders, Tobias, “Barnette Graphs with Faces up to Size 8 are Hamiltonian”. arXiv (2025). DOI 10.48550/arXiv.2508.03531. Definition 1.4, Theorem 1.12, Corollary 1.13, and Section 6. ↗ open copy ↗preprint · primary source · arXiv:2508.03531, checked 2026-08-01 · checked 2026-08-01Source use: original summary.States that the general problem remains unsolved and proves Hamiltonicity when every face has size at most 8, using a computer-aided analysis of 339,068,624 cases.Source used to assess the problem's recorded status.For Barnette’s conjecture: States that the general problem remains unsolved and proves Hamiltonicity when every face has size at most 8, using a computer-aided analysis of 339,068,624 cases.
Gunnar Brinkmann, Jan Goedgebeur, and Brendan McKay, “The minimality of the Georges–Kelmans graph”. Mathematics of Computation 91(335) (2021), 1483-1500. DOI 10.1090/mcom/3701. Abstract and Barnette-conjecture computation. ↗ open copy ↗journal article · primary source · checked 2026-08-01Source use: original summary.Verifies that every Barnette graph with at most 90 vertices is Hamiltonian.Source used to assess the problem's recorded status.For Barnette’s conjecture: Verifies that every Barnette graph with at most 90 vertices is Hamiltonian.
Jan Florek, “A Sufficient Condition for Cubic 3‐Connected Plane Bipartite Graphs to be Hamiltonian”. Journal of Graph Theory 110(3) (2025), 272-282. DOI 10.1002/jgt.23270. Abstract and main theorems. ↗ open copy ↗journal article · primary source · checked 2026-08-01Source use: original summary.Explicitly records the general problem as open and proves Hamiltonicity under face-adjacency restrictions.Source used to assess the problem's recorded status.For Barnette’s conjecture: Explicitly records the general problem as open and proves Hamiltonicity under face-adjacency restrictions.

Original TheoremDB editorial statement and source synthesis; external works are used for citation only.

[#P3070] Barnette’s conjecture

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance