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 that a finite simple 3-connected cubic bipartite plane graph is Hamiltonian if pairwise vertex-disjoint facial 4-cycles leave exactly six vertices uncovered. We also prove the at-most-six corollary, including impossibility of two uncovered vertices and existence of a matching in the original graph for four uncovered vertices. The chosen cycles need not include every quadrilateral face; other faces may have arbitrary even lengths. This record contains the revised paper PDF, manuscript source, and matching Lean 4 source snapshot. The formalization machine-checks the six-vertex theorem and at-most-six corollary. Verification notes give the pinned toolchain and full build procedure. 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.23032074
Primary Topic
Limits and Structures in Graph Theory
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)
Limits and Structures in Graph Theory
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 that a finite simple 3-connected cubic bipartite plane graph is Hamiltonian if pairwise vertex-disjoint facial 4-cycles leave exactly six vertices uncovered. We also prove the at-most-six corollary, including impossibility of two uncovered vertices and existence of a matching in the original graph for four uncovered vertices. The chosen cycles need not include every quadrilateral face; other faces may have arbitrary even lengths. This record contains the revised paper PDF, manuscript source, and matching Lean 4 source snapshot. The formalization machine-checks the six-vertex theorem and at-most-six corollary. Verification notes give the pinned toolchain and full build procedure. These conditional results do not resolve Barnette's conjecture in general.

Zenodo (CERN European Organization for Nuclear Research)
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.

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