Hamiltonicity of Barnette graphs with at most six vertices uncovered by disjoint facial 4-cycles

Barnette's conjecture asks whether every finite 3-connected cubic bipartite planar graph has a Hamiltonian cycle. We prove a sufficient condition for a finite simple 3-connected cubic bipartite plane graph: if a family of pairwise vertex-disjoint facial 4-cycles leaves at most six vertices uncovered, then the graph is Hamiltonian. The six-vertex case is the main theorem. The remaining cases include a proof that two uncovered vertices are impossible and that four uncovered vertices admit the required matching in the original graph. The paper also gives an infinite family satisfying the condition and examines its relation to earlier sufficient conditions. This record contains the corrected paper PDF, complete LaTeX manuscript source, and the Lean 4 formalization snapshot already released with version 1.1.0. The formalization checks both the six-vertex theorem and the at-most-six consequence with pinned dependencies. Verification and reproduction instructions are included. These conditional results do not resolve Barnette's conjecture in general.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-09-29
DOI
https://doi.org/10.5281/zenodo.23033585
Primary Topic
graph theory and CDMA systems
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

Hamiltonicity of Barnette graphs with at most six vertices uncovered by disjoint facial 4-cycles

Yiming Liu
Zenodo (CERN European Organization for Nuclear Research)
graph theory and CDMA systems
preprint

Hamiltonicity of Barnette graphs with at most six vertices uncovered by disjoint facial 4-cycles

Yiming Liu
preprint en

Abstract

Barnette's conjecture asks whether every finite 3-connected cubic bipartite planar graph has a Hamiltonian cycle. We prove a sufficient condition for a finite simple 3-connected cubic bipartite plane graph: if a family of pairwise vertex-disjoint facial 4-cycles leaves at most six vertices uncovered, then the graph is Hamiltonian. The six-vertex case is the main theorem. The remaining cases include a proof that two uncovered vertices are impossible and that four uncovered vertices admit the required matching in the original graph. The paper also gives an infinite family satisfying the condition and examines its relation to earlier sufficient conditions. This record contains the corrected paper PDF, complete LaTeX manuscript source, and the Lean 4 formalization snapshot already released with version 1.1.0. The formalization checks both the six-vertex theorem and the at-most-six consequence with pinned dependencies. Verification and reproduction instructions are included. These conditional results do not resolve Barnette's conjecture in general.

Zenodo (CERN European Organization for Nuclear Research)
graph theory and CDMA systems
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.

Hamiltonicity of Barnette graphs with at most six vertices uncovered by disjoint facial 4-cycles — Yiming Liu · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS