recategorized by
902 views
3 votes
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:

  1. $M$ is a maximum matching in $G$.
  2. $C$ is a minimum vertex cover in $G$.
  3. $G$ is a bipartite graph.

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

  1. Only statement $(1)$ is correct
  2. Only statement $(2)$ is correct
  3. Only statement $(3)$ is correct
  4. Only statements $(1)$ and $(2)$ are correct
  5. All the three statements $(1), (2),$ and $(3)$ are correct
recategorized by

1 Answer

3 votes
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.

Answer:

Related questions

4 votes
4 votes
2 answers
1