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

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\ge 3$) has at least $\frac{n+1}{2}$ near-perfect matchings which miss different vertices of $G$.