Tight bound for matching

Abstract

Let M be the number of edges in a maximum matching in graphs with m edges, maximum vertex degree k and shortest simple odd-length cycle length L. We show that

$$M\geq \left \{\begin{array}{l@{\quad }l}\frac{m}{2}-\frac{m}{2L},&\mbox{if}\ k=2,\\\noalign{\vspace{2pt}}\frac{m}{k}-\frac{m}{(k+L)k},&\mbox{if}\ k>2.\end{array}\right.$$

This lower bound is tight.

When no simple odd-length cycle exists it is known previously that $M\geq \frac{m}{k}$.