1
$\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$

I know that matching of size $|A|\implies|N(S)|\geq|S|\ \forall S\subseteq A$ is easy:

Proof: since there is a matching of size $|A|$ by looking at $G$ as the matching to which we added some edges we see the result right away.

But I was wondering about this proof that uses König's theorem ("In a bipartite graph the number of edges of a maximal cardinality matching is the same as the number of vertices in a minimum vertex cover"):

Proof 2: Let $M$ be the matching of size $|A|$. It is a maximal cardinality matching because it contains every vertex of $A$. By König's theorem any minimal vertex cover $U$ has $|U|=|A|$ vertices. If there was an $S\subseteq A$ such that $|N(S)|<|S|$ then by definition of neighborhood, $N(S)$ would touch the same edges as $S$ but with fewer vertices so $U'=[U\backslash S]\cup N(S)$ is of strictly smaller cardinality than $U$ and is also a vertex cover of $G$, which is impossible.

$\endgroup$
1
$\begingroup$

Well, this may be very late in coming and hopefully you've figured it out by now, but Konig's theorem is not about maximal but rather maximum cardinality matching. So it states that "In a bipartite graph the number of edges of a maximum cardinality matching is the same as the number of vertices in a minimum vertex cover". Hopefully that helps clear up the problem.

$\endgroup$

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.