 # Form of the smallest vertex cover in a bipartite graph I'm trying to write a proof of Konig's theor dream13rxs 2022-07-14 Answered
Form of the smallest vertex cover in a bipartite graph
I'm trying to write a proof of Konig's theorem using Menger's theorem. However, I got stuck along the way. In order to move forward I'd (apparently) need to show the following fact.
Let G be a bipartite graph with partite sets X and Y. The smallest vertex cover of G is of the form $\left(X-A\right)\cup N\left(A\right)$ for some $A\subseteq X$.
I tried doing a proof by contradiction but to no avail. Maybe the thesis I'm trying to show is false in the first place? Any help would be greatly appreciated.
You can still ask an expert for help

## Want to know more about Discrete math?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it zlepljalz2
Step 1
Let U be any vertex cover; let $A=X-U$ (the smallest set for which U contains $X-A$).
For every vertex $b\in N\left(A\right)$, there is some edge ab with $a\in A$ which needs to be covered by U somehow. By construction $a\notin U$, so ab is not covered by a. Therefore ab must be covered by b: we must have $b\in U$. Therefore $N\left(A\right)\subseteq U$.
Step 2
We have shown that U contains $\left(X-A\right)\cup N\left(A\right)$. We can check that $\left(X-A\right)\cup N\left(A\right)$ is a vertex cover all by itself. Therefore if U is a minimal vertex cover (if it has no proper subset which is a vertex cover) we must have $U=\left(X-A\right)\cup N\left(A\right)$. In particular, this is true of the smallest vertex cover.
I admit I do not see how you need this fact to prove Konig's theorem from Menger's theorem. Neither one deals in N(A) as a concept. Maybe you are trying to prove Hall's theorem from Konig's theorem?

We have step-by-step solutions for your answer!