@Deepak Poonia sir can you pls provide answer to this

Dark Mode

313 views

3 votes

We are given a graph $G$ along with a matching $M$ and a vertex cover $C$ in it such that $|M|=|C|$. Consider the following statements:

- $M$ is a maximum matching in $G$.
- $C$ is a minimum vertex cover in $G$.
- $G$ is a bipartite graph.

Which of the following is $\text{TRUE}$?

- Only statement $(1)$ is correct
- Only statement $(2)$ is correct
- Only statement $(3)$ is correct
- Only statements $(1)$ and $(2)$ are correct
- All the three statements $(1), (2),$ and $(3)$ are correct

@vivek18 Answered.

It is ALREADY Covered in **GO Classes Graph Theory Course**.

https://youtube.com/playlist?list=PLIPZ2_p3RNHjQoj0k-BlI9zXE0QKdl-lI

0

3 votes

Learn the WHOLE Concept, with Proof HERE:

https://youtu.be/UxUEZj_vPQo?t=3908

Theorem 1:

**The cardinality of ANY Matching is less than or equal to the cardinality of ANY Vertex Cover.**

Proof: Watch This.

Corollary of Theorem 1:

**Size of Maximum Matching is less than or equal to the size of Minimum Vertex Cover.**

Proof: Watch the above lecture.

So, the MAXIMUM matching you can create, will have size less than or equal to the size of MINIMUM Vertex Cover.

So, **when can a Matching $M$ & Vertex Cover $C$ be Same??**

That is possible only when $M$ is a maximum matching & $C$ is a minimum vertex cover.

So, Statement (1),(2) are correct.

Konig’s Theorem:

For a bipartite graph, the Matching number (i.e., size of a maximum matching) is equal to the vertex cover number (i.e., size of a minimum vertex cover).

https://youtu.be/UxUEZj_vPQo?t=5843

BUT this is only ONE WAY. i.e. If Matching number is same as Covering number, it doesn’t imply that the graph is Bipartite.

For counter example, Take a “complete graph K4 with one edge removed” graph, it has Matching Number 2, Vertex Covering Number 2, But it is Not bipartite.

So, Statement 3 is False.

EVERY Concept used in this question is covered, With Proof, in this lecture.

WATCH $\color{red}{\text{The COMPLETE Graph Theory Course, with ALL the Proofs, Questions, Variations}}$ etc, HERE

https://youtube.com/playlist?list=PLIPZ2_p3RNHjQoj0k-BlI9zXE0QKdl-lI

This playlist is ALL you need for ANY exam, and proper knowledge of Graph Theory.