Maximum matchings in regular graphs of high girth (Q870087)

Summary: 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)\).