Regular-graph matching bound from unmatched vertices (source code)

= Regular-graph matching bound from unmatched vertices

If a finite <simple graph> is $k$-regular with $k\geq1$ and has $n$ vertices has a maximum matching of size $m$, its unmatched vertices are independent. Counting their incident edges gives $k(n-2m)\leq2(k-1)m$, and hence $m\geq kn/(4k-2)$.