Degree-type Conditions for Bipartite Matching Extendability

Abstract

Let \(G\) be a simple connected graph containing a perfect matching. \(G\) is said to be BM-extendable if every matching \(M\) whose induced subgraph is a bipartite graph extends to a perfect matching of \(G\). In this paper, for recognizing BM-extendable graphs, we present some conditions in terms of vertex degrees, including the degree sum conditions, the minimum degree conditions, and the Fan-type condition. Furthermore, we show that all these conditions are best possible in some sense.