Hamiltonicity of Barnette graphs with 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. This preprint studies a sufficient condition for a fixed plane embedding. Let G be a finite simple 3-connected cubic bipartite plane graph, and let Q be a family of pairwise vertex-disjoint facial 4-cycles in that embedding. We prove that if exactly six original vertices of G lie outside the union of the cycles in Q, then G has a Hamiltonian cycle. The family need not contain every quadrilateral face, no restriction is imposed on the lengths of the other faces, and the order of G is unrestricted. This record contains the paper PDF and the corresponding Lean 4 source snapshot for machine checking the main theorem. The source snapshot records its Lean toolchain and pinned dependencies, and the accompanying verification notes explain how to rebuild and check the formal declaration. This is a result under the stated six-uncovered-vertex condition; it does 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.23028945
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 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 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. This preprint studies a sufficient condition for a fixed plane embedding. Let G be a finite simple 3-connected cubic bipartite plane graph, and let Q be a family of pairwise vertex-disjoint facial 4-cycles in that embedding. We prove that if exactly six original vertices of G lie outside the union of the cycles in Q, then G has a Hamiltonian cycle. The family need not contain every quadrilateral face, no restriction is imposed on the lengths of the other faces, and the order of G is unrestricted. This record contains the paper PDF and the corresponding Lean 4 source snapshot for machine checking the main theorem. The source snapshot records its Lean toolchain and pinned dependencies, and the accompanying verification notes explain how to rebuild and check the formal declaration. This is a result under the stated six-uncovered-vertex condition; it does 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 six vertices uncovered by disjoint facial 4-cycles — Yiming Liu · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS