67 views

The relation between size of a maximum matching $M_{d}$ in a disconnected graph G on vertex set V and the size of a maximum matching $M_{c}$ of a connected graph G on same vertex set V is

(A) $M_{d}$ < $M_{c}$

(B) $M_{d}$ $=$$M_{c}$

(C)$M_{c}$ $\geq$$M_{d}$

(D) None of the above.

think c is the answer. Comment if right
No its B they have given
Then i think they have given it wrong. Take 4 vertex and make a square. No of matching is 2 while now take a disconnected graph in which no edge is there . Matching = 0. so md < mc graph. now for equal case take the same vertex set make 2 components such that each component contain 2 vertex and one edge. so now maximal matching in such a graph is 2. which is equal to the mc.

Have a look at this:

Left half is disconnected graph.

So, here, Md<Mc.

This was from Gatebbok, right?