A Spectral Extremal Problem on Non-Bipartite Triangle-Free Graphs

A theorem of Nosal and Nikiforov states that if G is a triangle-free graph with m edges, then λ(G)≤ √m, equality holds if and only if G is a complete bipartite graph. A well-known spectral conjecture of Bollobás and Nikiforov [J. Combin. Theory Ser. B 97 (2007)] asserts that if G is a Kᵣ₊₁-free graph with m edges, then λ₁²(G) + λ₂²(G) ≤ (1-1/r)2m. Recently, Lin, Ning and Wu [Combin. Probab. Comput. 30 (2021)] confirmed the conjecture in the case $r=2$. Using this base case, they proved further that λ (G)≤ √m-1 for every non-bipartite triangle-free graph G, with equality if and only if $m=5$ and G=C₅. Moreover, Zhai and Shu [Discrete Math. 345 (2022)] presented an improvement by showing λ (G) ≤ β (m), where β(m) is the largest root of Z(x):=x³-x²-(m-2)x+m-3. The equality in Zhai--Shu's result holds only if m is odd and G is obtained from the complete bipartite graph K2,m-1/2 by subdividing exactly one edge. Motivated by this observation, Zhai and Shu proposed a question to find a sharp bound when m is even. We shall solve this question by using a different method and characterize three kinds of spectral extremal graphs over all triangle-free non-bipartite graphs with even size. Our proof technique is mainly based on applying Cauchy's interlacing theorem of eigenvalues of a graph, and with the aid of a triangle counting lemma in terms of both eigenvalues and the size of a graph.