$G$ has a bipartition $(X,Y)$, and matching $M$ so that $X$ is fully matched, show $\exists x \in X$ with all its edges belong to a maximal matching

81 Views Asked by At

Firstly, it was clear to me that $M$ might not be a bipartite matching, as nodes within $X$ might be matched to one another.

But what will our approach be to prove the existence of a vertex with all edges belonging to one of the possibly many maximal matchings?