[Math] Hall’s theorem for bipartite graphs using König’s theorem

bipartite-graphsgraph theorymatching-theoryproof-verification

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

Best Answer

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.

Related Question