A generalization of Petersen's matching theorem (Q2111920)

Matchings in graphs are extensively studied in the literature. One of the earliest results in graph theory is \textit{J. Petersen}'s theorem [Acta Math. 15, 193--220 (1891; JFM 23.0115.03)] which states that every cubic, bridgeless graph contains a perfect matching. By the classical result of \textit{H. Whitney} [Am. J. Math. 54, 150--168 (1932; Zbl 0003.32804)], the vertex-connectivity of a graph is at most its edge-connectivity, which in turn is at most the minimum degree. The well-known Petersen's theorem states that vertex-connectivity and edge-connectivity in a connected cubic graph are equal. Here, the authors generalize Petersen's theorem and also prove that for an odd integer \(k\) \((k\geq 3) \), if \(G\) is a \(2\)-connected \(k\)-regular graph of order \(n\), then \(\alpha(G)\geq (k^2+k+6/k^2+2k+3 )\times n/2\). The case when \(k\) is even behaving differently. In this case, for \(k\geq 4\) even, if \(G\) is a \(2\)-connected \(k\)-regular graph of order \(n\), then \(\alpha (G)\geq (k^2 + 4k/k^2+k+2)(n/2)\). For all \(k\geq 3,\) if \(G\) is a 2-connected graph of order \(n\) and maximum degree \(k\) that is not necessarily regular, then \(\alpha(G)\geq (2n/k+2)\). In all the above bounds, the extremal graphs are characterized. This article has many interesting results. It is useful to researchers working on coloring and matching of graphs.