A counterexample and a threshold theorem for graphs with two distinct eigenvalues

Le résumé fourni par la source

For a graph G on n vertices, q(G) denotes the minimum number of distinct eigenvalues among the real symmetric matrices whose off-diagonal zero pattern is prescribed by G. Barrett, Fallat, Furst, Nasserasr, Rooney and Tait (arXiv:2411.12917; ELA 42 (2026)) conjectured (their Conjecture 5.5) that if e(complement(G)) <= n-2 then q(G) = 3 precisely when complement(G) is a double star together with an isolated vertex, and q(G) = 2 otherwise. We show that G = K_{1,1,3} is a counterexample: its complement K_3 u 2K_1 has 3 = n-2 edges and is not a forest, yet q(K_{1,1,3}) = 3. We then prove that within the range e(complement(G)) <= n-2 the known obstruction produces exactly two families of graphs with q > 2, namely the double stars S_{a,b} u K_1 and the single graph K_3 u 2K_1; this yields the amended conjecture and explains why no obstruction of this kind exists below the threshold n-3 of the authors' Conjecture 1.1. On the constructive side we prove that every graph G with e(complement(G)) = n-2 whose complement is non-bipartite with a connected non-trivial component, other than K_{1,1,3}, satisfies q(G) = 2, exhibiting a bipartite/non-bipartite asymmetry at the threshold: the exceptions are an infinite bipartite family against a single non-bipartite graph. The counterexample and an infinite non-bipartite family attaining q = 2 have been formally verified in Lean 4 / Mathlib.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.