Large matchings from eigenvalues (Q869943)

Let \(G=(E,V)\) be a graph with edge set \(E\), vertex set \(V=\{1,2,\dots,n\}\) and corresponding degrees \(d_1, d_2, \dots, d_n\). The terms order and size refer to the numbers \(n = | V| \) of vertices and \(e=| E| \) of edges of \(G\), respectively. The eigenvalues of \(G\) are the eigenvalues \(\lambda_i\) of its adyacency matrix \(A\), indexed so that \(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n\). A classical result establishes that for any graph with \(n\) vertices and \(e\) edges, \[ \lambda_1 \geq \frac{2e}{n}. \] In this paper, the authors find different lower bounds for \(\lambda_1 - \frac{2e}{n}\). In particular, they show for all graphs \(G\) on \(n \geq 4\) vertices, \[ \lambda_1 - \frac{2e}{n} > \frac{1}{n(\Lambda+2)}, \] where \(\Lambda\) is the maximum of the vertex degrees in \(G\). By using this bound, the authors obtain eigenvalue conditions sufficient to imply the existence of large matchings in regular graphs.