The Gateway to Computer Science Excellence

+1 vote

Given a maximum matching M, if we pick one endpoint of each edge in M, this form a valid vertex cover.

TRUE

FALSE

TRUE

FALSE

+3 votes

Best answer

First of all we should know the terms "maximal matching" and "vertex cover"..

It is the maximal set of edges possible such that no two edges of this set intersect at any vertex..Maximal matching :

is a set ofVertex Cover : Itverticessuch that each edge of the graph is incident to at least onevertexof the set. In other words all edges should be covered by this set of vertices..

So consider a pentagon as graph in our example..

So for maximal matching we can have maximum of two edges as non intersecting...Now if we consider one endpoints of each edge , then we have two such vertices..

Now each of these vertices can cover only two edges and hence we can cover only 4 edges in total..Hence one edge will not be able to be covered using the given two vertices..Hence these two vertices wont constitute a vertex cover..

**Hence the given assertion is false ..**

52,375 questions

60,554 answers

201,952 comments

95,374 users