A higher-connectivity spectral Ore theorem for triangle-free graphs

Abstract

Let $B_{n,k}$ be the graph obtained from the balanced complete bipartite graph on $n$ vertices by deleting a matching of size $k$. If $G$ is an $n$-vertex triangle-free graph with $κ(\comp G)\geq k$, we prove that $\rhoA(G)\leq\rhoA(B_{n,k})$ for $n\geq4k+2$, with equality precisely when $G\cong B_{n,k}$, and we compute $\rhoA(B_{n,k})$ explicitly. We also solve the bipartite problem for every $n\geq2k+1$, determine the boundary value $\operatorname{spex}_κ(2k,K_3;k)=k-1$, and settle the full problem for $k=2$. In particular, $B_{n,2}$ is uniquely extremal exactly from order $6$ onward. For $k=1$, equivalently when the complement is connected, $B_{n,1}=K_{\ceil{n/2},\floor{n/2}}-e$ is uniquely extremal for every $n\geq3$.

Disclosure

“aplacian and normalized adjacency versions of Problems 5.1–5.2 appear to be unexplored. Declaration of generative AI and AI-assisted technologies in the manuscript preparation process During the preparation of this work, the authors used OpenAI Codex to discuss proof strategies, organize and check bibliographic information, check algebraic calculations and proof exposition, and improve language and readability. After using this tool, the authors reviewed and edited the content as”

PDF page 19

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:09:39.041292Z

Structural counts