Is the following claim on saturated matching on bipartite graphs with constrained degree true?

25 Views Asked by At

Claim: A bipartite graph $G(X, Y)$ with all vertices in $X$ having degree less than or equal to 2 has an X saturating matching if and only if for any connected component $G'(X', Y')$ in $G$, $|X'| \geq |Y'|$.

I came across this by myself but could not find any literature on this. Any help would be appreciated

A matching is X saturated iff all vertices in X are matched

1

There are 1 best solutions below

0
On

The claim as you have stated is false. Consider a path of length $2$, with $3$ vertices.