Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# DM - Grand Test -Q11

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+1 vote

Which edge or pair of edges below CANNOT be extended to obtain a maximum cardinality matching for this graph? This is, which edge or pair of edges does NOT form a proper subset of a maximum cardinality matching?

(A) (I, J)

(B) (A, B) and (K, L)

(C) (C, D) and (J, K)

(D) (D, E) and (J, K)

edited Sep 9, 2020

Matching in Graphs :

Let G be a graph. Two edges are independent if they have no common endvertex. A set M of independent edges of G is called a matching. The matching number, denoted &micro;(G), is the maximum size of a matching in G.

http://www-sop.inria.fr/members/Frederic.Havet/Cours/matching.pdf

For this given graph, we have a perfect matching that is of size 6. So, maximum cardinality of matching is 6.

Consider option C :

If you take  (C, D) and (J, K) in the matching then you cannot make 6 cardinality matching. At most 5 cardinality matching we can make.
answered Sep 9, 2020 by (226,240 points)