4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I think you're talking about an* edge cover of G. Or do you mean a minimal edge cover? And I also think that $|X|=|\beta|$ in the third paragraph of your proof is always true, and not because of Konig Egervary. $\endgroup$
    – Algebear
    Nov 11 '20 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.