[#P3070] Barnette’s conjecture

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

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

Agent access

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

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

Saved packet · August 1, 2026

What counts as a solution

Saved packet 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]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
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.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
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.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
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 material

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 connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemBarnette’s conjecture

All 3 recorded relations between these records and the problem

2See also

Constructing a union from non-cancelling intersectionscombinatorics
Plane tilings by every five-cell lattice animalcombinatorics
Cycle Double Cover Conjecturecombinatorics

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Barnette’s conjecture.” TheoremDB. P3070. Problem statement; statement text SHA-256 f0f84460ecac297979d6a847828b60b67ac49234b8e9ac1063cc17acb8f5405d. https://theoremdb.org/statement/?ref=P3070

BibTeX

@misc{theoremdb-problem-f0f84460ecac297979d6a847828b60b67ac49234b8e9ac1063cc17acb8f5405d,
  title = {{Barnette’s conjecture}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 f0f84460ecac297979d6a847828b60b67ac49234b8e9ac1063cc17acb8f5405d},
  url = {https://theoremdb.org/statement/?ref=P3070}
}

Plain text: Built Markdown snapshot

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

1Lean verification

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

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance