On the Structure of Graphs with Exactly Two Near-Perfect Matchings

Hong Lin1
1School of Sciences, Jimei University, Xiamen, Fujian, 361021, P.R.China

Abstract

A near-perfect matching is a matching saturating all but one vertex in a graph. In this note, it is proved that if a graph has a near-perfect matching then it has at least two, moreover, a concise structure construction for all graphs with exactly two near-perfect matchings is given. We also prove that every connected claw-free graph \(G\) of odd order \(n\) (\(n \geq 3\)) has at least \(\frac{n+1}{2}\) near-perfect matchings which miss different vertices of \(G\).