SAMS Subject Classification Number: 6

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 \(G\) is a \(2\)-connected \(3\)-regular graph of order \(n\), then \(\alpha'(G) = \frac{1}{2}n\), where \(\alpha'(G)\) denotes the matching number of \(G\). We generalize Petersen’s theorem and prove that for \(k \ge 3\) an odd integer, if \(G\) is a \(2\)-connected \(k\)-regular graph of order \(n\), then \(\alpha'(G) \ge \left( \frac{k^2 + k + 6}{k^2 + 2k + 3} \right) \times \frac{n}{2}\). The case when \(k\) is even behaves differently. In this case, for \(k \ge 4\) even, if \(G\) is a \(2\)-connected \(k\)-regular graph of order \(n\), then \(\alpha'(G) \ge \left( \frac{k^2 + 4}{k^2 + k + 2} \right) \times \frac{n}{2}\). For all \(k \ge 3\), if \(G\) is a \(2\)-connected non-regular graph of order \(n\) and maximum degree \(k\), then we show that \(\alpha'(G) \ge \frac{2n}{k + 2}\). In all the above bounds, the extremal graphs are characterized.