Hall's theorem for bipartite graphs using König's theorem

Question

Theorem: Let $G=(A\cup B,E)$ be a bipartite graph and for each $S\subseteq A$ let $$N(S)=\{v\in B\ :\ \exists u\in S\text{ such that}\{u,v\}\in E\}$$

Then, $G$ has a matching of size $|A|$ if and only if $|N(S)|\geq|S|$ for all $S\subseteq A$

My proof for the direction $\nexists$ a matching of size $|A|\implies\exists S\subseteq A$ s.t. $|N(S)|<|S|$ requiers the following theorem:

König's theorem: In a bipartite graph $G$ the number of edges of a maximal cardinality matching is the same as the number of vertices in a minimum vertex cover of $G$

My proof (of this direction of Hall's):

If there is no matching of size $|A|$ then any maximal cardinality matching $M$ will satisfy $|M|<|A|$ since a maximum cardinality matching cannot have more edges than $A$ or $B$ (so not more than min{|A|,|B|}) in the context of a bipartite graph. Let $U$ be a minimal vertex cover of $G$, by König's theorem $|U|=|M|<|A|$ so $\exists v\in A$ a non isolated vertex (otherwise it would have to be in $U$) and s.t. $\notin U$. Since $U$ is a vertex cover, it must cover any edge connected to $v$. So there is a vertex $b\in B\cap U$ connected to $v$ by an edge and to at least some other vertex in $A$ (otherwise it would be an isolated edge, which would have to be in the maximal cardinality matching $M$) by considering the neighbors of $b$ in $A$ and their neighbors in $B$ and their neighbors in $A$ etc... this is the part where I'm sure we arrive at a subset $S\subseteq A$ (with $v\in S$) with smaller neighborhood in $B$ but don't know how to proove it...

Any help would be appreciated, thanks

Answer 1

Probably you know how to finish this proof but I will try to write it out for anyone who might need it.

As you have noted, we must find a subset $S$ that contradicts the hypotheses so that the theorem is proved by contradiction.

1. Because we are supposing that $|U|< |A|$, this means that $$|U| = |U \cap A| + |U \cap B| < |A|$$ this in turns means that the following inequality must hold: $$ |U \cap B| < |A| - |U \cap A|$$ Let $S = A \setminus (A \cap U)$.

2. The vertex $v \in A \setminus U$ can only be connected to vertex $b \in B \cap U$ otherwise we could extend the cover contradicting the fact that $U$ is a of the vertex cover of $G$. This means that $N(S) \leq |U \cap B|$.

Combining the inequalities obtained in (1) and (2) we get that $$|N(S)| < |S|$$ and so the theorem is proved by contradiction.

Comment: This proof is the same as the one in Diestel's Graph theory wonderful text.

Answer 2

I write an approach for it.

$( \Longleftarrow)$ Let $G = (X \cup Y,E) $ be a bipartite graph that satisfies Hall’s condition, $|N(S)| \geq |S|, \forall S \subset X$. We want to show that there is a matching of $X$ into $Y$. For it, let $\beta$ be a maximum matching. By the König-Egerváry theorem, there is an edge cover of size $|\beta|$.

Now, let $A$ be the set of vertices of the edge cover that are in $X$, $B = X-A$, and $C$ the set of vertices of the edge cover that are in $Y$ .

Then we have that for König Egervàry that $|A|+|B|=|\beta|$ and for definition of $A$ and $B$, $|A|+|B|=|X|$. Finally $|B| \leq |N(B)| \leq |C|$ it is the first of these is Hall’s condition and the second is because $N(B) \subseteq C$. Indeed, if $b \in B$ has a neighbor $c\notin C$, then $ac$ is an edge not covered by the edge cover.

So we get $|X| \leq |A| + |C|$ also $|X| \leq |\beta|$. In other words, the maximum matching has size at least the size of $X$. But since each edge of $\beta$ uses a vertex of $X$, and each vertex can be used at most once, it must be that $|X| = |M|$, and $M$ saturates $X$. This proves Hall.

$(\implies)$ If there is a matching of $X$ into $Y$, so $\forall S \subset X$, we get $|S|\leq |N(S)|$.

This proves Hall's Theorem.