Essential Vertex in Connected Non-Trivial Bipartite Graph

Question

I have been struggling with the following problem for a long time now and so decided to ask if anybody could offer some help.

We have a connected bipartite non-trivial graph $G$ with bipartition $(X,Y)$. What we need to show is that there exists a vertex s.t. it is saturated by every maximum matching.

My attempt: Let M be a maximum matching. Choose a vertex $x$ in $X$ s.t. it is not saturated by M. We can choose such vertex because if every vertex of X is saturated with respect to M, then we are essentially done, since any of them will be saturated by any maximum matching.

Now, let $N(x)$ be the set of neighbors of $x$. I want to show that every vertex in $N(x)$ will be saturated with respect to any maximum matching. Observe that every vertex in $N(x)$ is saturated in $M$ since otherwise we would have an $M$-augmenting path, which would contradict maximality of $M$.

Let $M’$ be any other maximum matching. Then if $M’$ does not saturate $x$, then again it must saturate all of the vertices in $N(x)$, because otherwise there would be an $M’$-augmenting path.

Now if $M’$ saturates $x$, I m stuck. I want to show that still all of the vertices in $N(x)$ are saturated, but I cannot think of any argument.

Answer 1

According to Hall's marriage theorem, a matching saturates a partite set A if and only if for each subset S in A, $|N(S)| \ge |S|$. if that is the case in our graph for the partite set X then we are done. otherwise there must be a minimal subset S in X where $|N(S)| < |S|$. being minimal, it means there cannot be a subset $T \subseteq N(S)$ where $|N(T) \cap S| < |T|$, otherwise you can delete T and their neighbors in S and get a smaller subset $S' \subseteq S$ satisfying $|N(S')| < |S'|$.

So again due to Hall's marriage theorem, $N(S)$ can be fully saturated by a matching to vertices in S which on their part can only pair up with vertices in $N(S)$. so if there is a matching not saturating $N(S)$, you can always enlarge it by matching all of $N(S)$ with vertices of S instead.

Answer 2

Suppose there exists a vertex $u \in N(x)$, which is not saturated by $M'$. We have already proved that every vertex in $N(x)$ is saturated under $M$. Hence there exists vertex $u_1$ s.t. $uu_1 \in M$, where $uu_1$ denotes an edge.

Consider $u_1$ under $M'$. If $u_1$ is unsaturated by $M'$, then we have an $M'$-augmenting path: $uu_1$ and we are done, since $M'$ was maximal, hence we reached contradiction. Else, suppose $u_1$ is saturated under $M'$, i.e., there exists $u_2$ s.t. $u_1u_2 \in M'$.

Now consider $u_2$ under original matching $M$. If $u_2$ is unsaturated under $M$, we have $M$-augmenting path: $xuu_1u_2$ that leads to contradiction. Else, $u_2$ is saturated in $M$. Then there exists $u_3$ s.t. $u_2u_3 \in M$.

Continuing in this manner, we obtain contradiction at each step. Since the graph is finite, it must be that $u$ is saturated under $M'$. Since $u$ was arbitrary, we conclude that every vertex in $N(x)$ is saturated under $M'$, which was also arbitrary maximum matching.

Therefore, every vertex in $N(x)$ is essential, i.e., is saturated under every maximum matching.

One last thing to clarify: since $G$ is connected, we are guaranteed that $|N(x)|\geq1$. Hence, we are assured that such vertex saturated under each maximum matching exists.