Matching and edge-connectivity in regular graphs

AbstractHenning and Yeo proved a lower bound for the minimum size of a maximum matching in a connected k-regular graph with n vertices; it is sharp infinitely often. In an earlier paper, we characterized when equality holds. In this paper, we prove a lower bound for the minimum size of a maximum matching in an l-edge-connected k-regular graph with n vertices, for l≥2 and k≥4. Again it is sharp for infinitely many n, and we characterize when equality holds in the bound