A generalization of Petersen's matching theorem

One of the earliest results in graph theory is Petersen's matching theorem from 1891 which states that every bridgeless cubic graph contains a perfect matching. Since the vertex-connectivity and edge-connectivity in a connected cubic graph are equal, Petersen's theorem can be stated as follows: If Gis a 2-connected 3-regular graph of ordern, then alpha ' (G) = 1/2n, where alpha ' (G) denotes the matching number of G. We generalize Petersen's theorem and prove that for k >= 3an odd integer, if Gis a 2-connected k-regular graph of order n, then alpha ' (G) >= (k(2)+k+6/ k(2)+ 2k+3) x n/2. The case when kis even behaves differently. In this case, for k >= 4 even, if G is 2-connected k-regular graph of ordern, then alpha ' (G) >= (k(2)+4 / k(2)+ k+2 ) n/2. For all k >= 3, if Gis a 2-connected graph of ordernand maximum degreekthat is not necessarily regular, then we show that alpha ' (G) >= 2n/k+2. In all the above bounds, the extremal graphs are characterized. (c) 2022 Elsevier B.V. All rights reserved.