Forest certificates and Hamilton cycles in Barnette graphs with at most six uncovered vertices

Barnette's conjecture asks whether every finite 3-connected cubic bipartite planar graph has a Hamiltonian cycle. We show that, for a finite simple 3-connected cubic bipartite plane graph, pairwise vertex-disjoint facial 4-cycles leaving at most six vertices uncovered force a colour-constrained partition of the big faces into two induced forests. Every edge internal to these forests has an endpoint in a set of at most three big faces of one colour. This certificate yields a Hamiltonian cycle through Florek's criterion. We also give an independent direct proof using residual matchings, connectivity after edge deletion, and expansion of the facial cycles. A verified 66-vertex example attains the three-face bound and fails a simpler two-colour forest condition; an unbounded family realizes the no-matching branch. This record contains the revised paper PDF, complete LaTeX source, reproducibility files, and a pinned Lean 4 snapshot formalizing the exactly-six and at-most-six Hamiltonicity results and the forest certificate. The edge-control refinement and broader two-active-face proposition are proved in the paper. The paper and data are CC BY 4.0; original Lean and Python code is Apache-2.0. These conditional results do not resolve Barnette's conjecture.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-09-29
DOI
https://doi.org/10.5281/zenodo.23041884
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

Forest certificates and Hamilton cycles in Barnette graphs with at most six uncovered vertices

Yiming Liu
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Forest certificates and Hamilton cycles in Barnette graphs with at most six uncovered vertices

Yiming Liu
preprint en

Abstract

Barnette's conjecture asks whether every finite 3-connected cubic bipartite planar graph has a Hamiltonian cycle. We show that, for a finite simple 3-connected cubic bipartite plane graph, pairwise vertex-disjoint facial 4-cycles leaving at most six vertices uncovered force a colour-constrained partition of the big faces into two induced forests. Every edge internal to these forests has an endpoint in a set of at most three big faces of one colour. This certificate yields a Hamiltonian cycle through Florek's criterion. We also give an independent direct proof using residual matchings, connectivity after edge deletion, and expansion of the facial cycles. A verified 66-vertex example attains the three-face bound and fails a simpler two-colour forest condition; an unbounded family realizes the no-matching branch. This record contains the revised paper PDF, complete LaTeX source, reproducibility files, and a pinned Lean 4 snapshot formalizing the exactly-six and at-most-six Hamiltonicity results and the forest certificate. The edge-control refinement and broader two-active-face proposition are proved in the paper. The paper and data are CC BY 4.0; original Lean and Python code is Apache-2.0. These conditional results do not resolve Barnette's conjecture.

Zenodo (CERN European Organization for Nuclear Research)
Life in Land
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Forest certificates and Hamilton cycles in Barnette graphs with at most six uncovered vertices — Yiming Liu · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS