A tight lower bound on matching number of graphs

Xiaofeng Gu, Muhuo Liu

Published 2021-03-22Version 1

The matching number of a graph $G$, denoted by $\alpha'(G)$, is the size of a maximum matching in $G$. The matching number of regular graphs has been well studied, however, not as much is known for general graphs. Haxell and Scott gave a complete description for the lower bound on the matching number of a graph with maximum degree at most 3 in terms of the number of vertices with fixed degree. Similar idea was used by Henning and Yeo, who established a tight lower bound on the matching number of a graph with given maximum degree in terms of the numbers of vertices and edges. We discover a tight lower bound on the matching number of general graphs via eigenvalues of combinatorial Laplacian. Let $\mu_i$ denotes the $i$th smallest eigenvalue of the Laplacian matrix of a graph. In this paper, we show that $\alpha'(G)\ge \min\{\frac{\mu_2}{\mu_n}(n -1), \frac{1}{2}(n-1)\}$ for a nonempty graph $G$ on $n$ vertices, strengthening a theorem of Brouwer and Haemers who showed that if $2\mu_2 \ge \mu_n$, then $G$ has a perfect matching. Moreover, the lower bound is tight. We contribute a useful lemma in the proof, which is of its own interest, and as applications, we prove similar results for factor-critical graphs, the number of balloons, spanning even subgraphs, as well as spanning trees with bounded degree.