Answer D : only statement (1) and (2) are correct.
Reason behind asking this Question :
Kőnig's theorem :
“ In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover. ”
The given question is converse of this theorem which may or may not be true.
Solution :
Let,
$m$ be any matching, $M$ be maximum matching. $|m| \leq |M|$
$c$ be any vertex cover, $C$ be minimum vertex cover $|C| \leq |c|$
By definitions of maximum Matching and minimum Vertex Cover $|M|\leq|C|$
( For $n$ edges in matching all $2n$ points are distinct so vertex cover must have at least $n$ points. )
hence, $|m| \leq |M|\leq |C| \leq |c|$ meanig $\forall (m,c)\space |m|\leq |c|$
Now it is given that,
$|m|=|c|$
- Let $c$ is not minimum vertex cover. It means we can remove one or more vertices from $c$ and it will still be a vertex cover but doing so $|m|>|c-1|$ which is not possible if $(c-1)$ is a vertex cover hence, $c$ is minimum vertex cover.
- Similarly adding edge to $m$ makes $|m+1| > |c|$ which means $(m+1)$ is not a matching, so $m$ is maximum matching.
- Now to prove that converse of Kőnig's theorem may not be always true we need to find a non-bipartite graph where $|m|=|c|$
Take example of $4$ vertex graph with $M=$ { $(V_1,V_2),(V_3,V_4)$ }and $C=$ { $V_1,V_3$ }
here $|M|=|C|=2$ and graph is not bipartite ( has cycle of odd length $=3$ )
