# P3070: Barnette’s conjecture

- ID: `P3070`
- Reference: `barnette-conjecture`
- Page: https://theoremdb.org/statements/P3070
- Record maturity: Reviewed problem with recorded work

## Problem

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

### Context

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.

### Problem setup

- **Definition (cubic).** Every vertex has degree 3.
- **Definition (3-connected).** Deleting any two vertices leaves the graph connected.
- **Definition (Hamiltonian cycle).** A cycle that visits every vertex exactly once.
- **Remark.** 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.

### What 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.

## 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. [1](#reference-1) [2](#reference-2) [3](#reference-3) [4](#reference-4)

## Work

### Evidence for the current status

**Claim 1 (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.

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.

### Background and intake notes

- 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.
- The release review checked 4 structured sources on 2026-08-01.
- 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.

### Other known results

- **Claim 2** (supported): 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](#reference-1) [2](#reference-2) [3](#reference-3) [4](#reference-4)

### Prior approaches

- **Route 1** (supported): 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](#reference-1) [2](#reference-2) [3](#reference-3) [4](#reference-4)

### Open directions

- **Route 2** (reported): 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `barnette-conjecture`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://doi.org/10.4230/LIPIcs.GD.2025.6
   - 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
   - proceedings_article; primary source; checked 2026-08-01
   - Open copy: https://drops.dagstuhl.de/storage/00lipics/lipics-vol357-gd2025/html/LIPIcs.GD.2025.6/LIPIcs.GD.2025.6.html
   - Source 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.
   - 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.
2. <a id="reference-2"></a>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 https://doi.org/10.48550/arXiv.2508.03531
   - preprint; primary source; arXiv:2508.03531, checked 2026-08-01; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2508.03531
   - Source 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.
3. <a id="reference-3"></a>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 https://doi.org/10.1090/mcom/3701
   - journal_article; primary source; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2101.00943
   - Source 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.
4. <a id="reference-4"></a>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 https://doi.org/10.1002/jgt.23270
   - journal_article; primary source; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2309.09578
   - Source 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.