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

TRUE

FALSE
in Revision | 157 views

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

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

Vertex Cover :   It is a set of vertices such that each edge of the graph is incident to at least one vertex of 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 ..

by Veteran (102k points)
selected