Chartrand, Gary; Kapoor, S. F.; Oellermann, Ortrud R.; Ruiz, Sergio On maximum matchings in cubic graphs with a bounded number of bridge- covering paths. (English) Zbl 0653.05055 Bull. Aust. Math. Soc. 36, 441-447 (1987). Theorem: If the bridges of a connected cubic graph G of order p lie on r edge-disjoint paths of G, then each maximum matching of G contains at least p/2-\(\lfloor 2r/3\rfloor\) edges. This generalizes the classical results of J. Petersen [Acta Math. 15, 163-220 (1891)] and A. Errera [Mathesis 36, 56-60 (1922)] stating the existence of a perfect matching in the case of at most two bridges and, more general, in case \(r\leq 1\), resp. Moreover, the authors show by constructing a concerning graph G, that their result is best possible. For proving both the theorem and its sharpness the following theorem (due to C. Berge?) is used essentially, which couldn’t be found in the given references by the reviewer: Let G be a cubic graph of order p and let \(\ell\) be an integer with \(0\leq \ell \leq p/2\). Then every maximum matching of G has at least (p- 2\(\ell)/2\) edges if and only if for every proper subset S of V(G), the number of odd components of G-S does not exceed \(| S| +2\ell\). Reviewer: W.Wessel MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C35 Extremal problems in graph theory Keywords:bridges; maximum matching; perfect matching PDFBibTeX XMLCite \textit{G. Chartrand} et al., Bull. Aust. Math. Soc. 36, 441--447 (1987; Zbl 0653.05055) Full Text: DOI References: [1] DOI: 10.1007/BF02392606 · JFM 23.0115.03 [2] Errera, Mathesis 36 pp 56– (1922) · JFM 57.0755.07 [3] DOI: 10.1112/jlms/s1-22.2.107 · Zbl 0029.23301 [4] DOI: 10.1073/pnas.43.9.842 · Zbl 0086.16202 [5] Chartrand, Congressus Numerantium 41 pp 131– (1984) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.