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
- Antoine Delorme
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