Discrete

Question

In the above graph, find a maximum matching M. Then |M| is 
 

Answer 1

In matching a vertex can be present at most once.

Among the vertex 1, 2, 3, 4, 5. We are going to miss the one vertex either it is 1, 3 or 5. In the image 3 is absent in matching.

Now, we are left with 5 more vertices, With 5 vertices we can't have 3 pairs of different vertices. We can only have 2 pairs of different vertices.

Ans: $\left | M \right |$ = 4