Maximum Matchings in Regular Graphs of High Girth

Abstract

Let $G=(V,E)$ be any $d$-regular graph with girth $g$ on $n$ vertices, for $d \geq 3$. This note shows that $G$ has a maximum matching which includes all but an exponentially small fraction of the vertices, $O((d-1)^{-g/2})$. Specifically, in a maximum matching of $G$, the number of unmatched vertices is at most $n/n_0(d,g)$, where $n_0(d,g)$ is the number of vertices in a ball of radius $\lfloor(g-1)/2\rfloor$ around a vertex, for odd values of $g$, and around an edge, for even values of $g$. This result is tight if $n < 2n_0(d,g)$.