Alternating frames, K4 and the Petersen graph: a parity obstruction for zero-diagonal matrices of line graphs

Let H be a 2-edge-connected cubic graph. Each alternating circuit of H (a component of the symmetric difference of two perfect matchings) is even and so carries its own 2-colouring. We show that these local 2-colourings, restricted to the ends of the ears of each circuit, glue into one global 2-colouring of V(H) if and only if every brick in the tight cut decomposition of H is K4 or the Petersen graph; by a theorem of Joshi, Raghul, Diwan and Kothari, equivalently, iff every brick is θ-free. The question comes from linear algebra: for a graph G let ι0(G) be the minimum number of negative eigenvalues of a real symmetric matrix with zero diagonal and off-diagonal nonzero pattern E(G); the ordered matching number νo(G) is a lower bound. For every connected H with a perfect matching on n vertices, νo(L(H)) = n/2 − 1, with equality ι0 = νo for bipartite H. The gluing condition is equivalent to the consistency of a GF(2) system Σ(H) expressing that all blocks A[V∖W, W] indexed by perfect matchings W can be simultaneously deficient; when it fails, ι0(L(H)) ≥ n/2 > νo(L(H)). This holds for the odd prisms and the Möbius ladders on 4j vertices; consistency does not suffice for equality (an exact counterexample on 14 vertices). Important: this work was produced with substantial assistance from AI systems (Claude, Anthropic): several AI agents worked independently on proofs, prior-art search and verification. Proofs and computations were checked by independent AI reviewing agents (reports included in the archive) and by exact computation, but have NOT been reviewed by a human specialist. The proofs of the main results (Theorem G, Section 5; Theorem F, Section 6) were checked by independent AI reviewers (one definitional defect found and corrected) and by exhaustive computation on all bridgeless cubic graphs up to 18 vertices. A Lean 4 / Mathlib proof of the smallest obstruction (the triangular prism) is included. The prior-art search is necessarily incomplete; its limits are listed in the paper. Code (MIT licence), certificates and reports are included.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-17
DOI
https://doi.org/10.5281/zenodo.24295162
Primary Topic
Graph theory and applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Alternating frames, K4 and the Petersen graph: a parity obstruction for zero-diagonal matrices of line graphs

Antoine Delorme
3 links
Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
preprint

Alternating frames, K4 and the Petersen graph: a parity obstruction for zero-diagonal matrices of line graphs

Antoine Delorme
preprint en

Abstract

Let H be a 2-edge-connected cubic graph. Each alternating circuit of H (a component of the symmetric difference of two perfect matchings) is even and so carries its own 2-colouring. We show that these local 2-colourings, restricted to the ends of the ears of each circuit, glue into one global 2-colouring of V(H) if and only if every brick in the tight cut decomposition of H is K4 or the Petersen graph; by a theorem of Joshi, Raghul, Diwan and Kothari, equivalently, iff every brick is θ-free. The question comes from linear algebra: for a graph G let ι0(G) be the minimum number of negative eigenvalues of a real symmetric matrix with zero diagonal and off-diagonal nonzero pattern E(G); the ordered matching number νo(G) is a lower bound. For every connected H with a perfect matching on n vertices, νo(L(H)) = n/2 − 1, with equality ι0 = νo for bipartite H. The gluing condition is equivalent to the consistency of a GF(2) system Σ(H) expressing that all blocks A[V∖W, W] indexed by perfect matchings W can be simultaneously deficient; when it fails, ι0(L(H)) ≥ n/2 > νo(L(H)). This holds for the odd prisms and the Möbius ladders on 4j vertices; consistency does not suffice for equality (an exact counterexample on 14 vertices). Important: this work was produced with substantial assistance from AI systems (Claude, Anthropic): several AI agents worked independently on proofs, prior-art search and verification. Proofs and computations were checked by independent AI reviewing agents (reports included in the archive) and by exact computation, but have NOT been reviewed by a human specialist. The proofs of the main results (Theorem G, Section 5; Theorem F, Section 6) were checked by independent AI reviewers (one definitional defect found and corrected) and by exhaustive computation on all bridgeless cubic graphs up to 18 vertices. A Lean 4 / Mathlib proof of the smallest obstruction (the triangular prism) is included. The prior-art search is necessarily incomplete; its limits are listed in the paper. Code (MIT licence), certificates and reports are included.

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

Laika access coming soon