The Gateway to Computer Science Excellence
0 votes

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

in Revision by (21 points) | 60 views

1 Answer

+1 vote
Best answer

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

by Boss (16.3k points)
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,476 answers
100,384 users