Let $G$ be an $X,Y$-bigraph. Show that the following are equivalent.
a) $G$ is connected and every edge appears in some perfect matching.
b) $G$ has exactly two minimum vertex covers, $X$ and $Y$.
c) $|X|=|Y|$ and every nonempty $W \nsubseteq X$ satisfies $|N(W)| \geq |W|+1$.
I want to say that since we have a perfect matching, doesn't that immediately imply that $|X|=|Y|$? I'm not sure how to word my proof for these because I feel like some things are implied directly.
Best Answer
a -> b: we will assume a third minimum vertex cover and reach contradiction. a third vertex cover will consist of a subset $X' \subset X$ and a subset $Y' \subset Y$. $X - X'$ and $Y - Y'$ thus share no edges. it means that in every perfect matching $X - X'$ is matched with $Y'$ and $Y - Y'$ is matched with $X'$. $X'$ and $Y'$ must have edges between them otherwise G is not connected, however these edges cannot be a part of any perfect matching, leading to a contradiction.
b -> c: if for some $Y' \subset Y$: $|N(Y')| \leq |Y'|$, then $Y - Y' + N(Y')$ is a vertex cover with length equal or smaller than $Y$.
c -> a: first a proof by contradiction that G is connected. for a maximal disconnected component $G' \subset G$, $|G' \cap Y| +1\leq |G' \cap X|$ since the Y part of $G'$ has at least $|N(G' \cap Y)| + 1$ many neighbors. however the part of Y not in $G'$ also has more neighbors than its length, so it must have a neighbor in $G' \cap X$, leading to a contradiction. we will now construct a perfect matching using any arbitrary edge. for any edge $xy$ we can construct a perfect matching between $X-x$ and $Y-y$. by removing $y$ from $Y$, it is still true that for any $Y' \subset Y-y$: $|N(Y')| \geq Y'+1$, removing $x$ from $X$ still leaves us with $|N(Y')| \geq Y'$, which is Hall's marriage theorem condition for a perfect matching. add the edge $xy$ to the mix and we have a perfect matching between $X$ to $Y$ using any arbitrary edge $xy$.