2026/07/27 by Pei Liu, Feiyu Nan, Suil O +1
#math.CO
The Randić index of a graph G is R(G)=∑uv∈ E(G)1/ √(d(u)d(v)), where d(v) is the degree of v, and the matching number α'(G) is the maximum size of a matching in G. We prove that every n-vertex König--Egerváry graph, and in particular every bipartite graph, satisfies R(G)≤√(α'(G)(n-α'(G))), and we characterize the graphs attaining equality. Combining this with the Berge--Tutte formula, we determine the maximum of R(G)-α'(G) over all n-vertex graphs with n≥4, together with every extremal graph. This settles a conjecture of Aouchiche, Hansen, and Zheng from 2006 in the negative: the smallest counterexample is K10,55, the optimal part size is determined by the proportion (2-√2)/(4) rather than by \frac17, and the extremal graphs are not only the complete bipartite ones, so that the equality statement fails already for n=10. The two proportions give asymptotic slopes differing by 3.7⋅10-5, which explains why the conjecture resisted searches over graphs of small order, and the orders admitting two optimal part sizes are those arising from the Pell equation x2-2y2=1.