Median eigenvalues of subcubic graphs
The question is whether the median eigenvalues of every connected subcubic graph lie in [-1,1], the Heawood graph excepted. This resolves open problems of Fowler–Pisanski and Mohar.
The argument uses Cauchy interlacing through positive and negative tail estimates relative to a maximum cut. It then performs an extensive case analysis of local configurations: cut enhancers and positive and negative tail reducers. As an independent check, the case analysis and its use in Lemmas 2.7 and 2.8 were formalized in Lean 4 with Codex and an OpenAI GPT model. The authors reviewed the formal statements.
The median eigenvalues of every connected subcubic graph other than the Heawood graph are at most 1 in absolute value, and a positive-fraction strengthening is also proved. The ancillary Lean project builds successfully.
