The Gateway to Computer Science Excellence
+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 by (21 points) | 157 views

1 Answer

+3 votes
Best answer

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 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,497 answers
195,489 comments
100,803 users