## Abstract

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 [Formula presented], where α^{′}(G) denotes the matching number of G. We generalize Petersen's theorem and prove that for k≥3 an odd integer, if G is a 2-connected k-regular graph of order n, then [Formula presented]. The case when k is even behaves differently. In this case, for k≥4 even, if G is a 2-connected k-regular graph of order n, then [Formula presented]. For all k≥3, if G is a 2-connected graph of order n and maximum degree k that is not necessarily regular, then we show that [Formula presented]. In all the above bounds, the extremal graphs are characterized.

Original language | English |
---|---|

Article number | 113263 |

Journal | Discrete Mathematics |

Volume | 346 |

Issue number | 3 |

DOIs | |

Publication status | Published - Mar 2023 |

## Keywords

- 2-Connected graph
- Matching number
- Maximum degree

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics