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

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

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.

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.

• 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. Nov 11, 2020 at 21:51