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.


in Revision by | 211 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 ..

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
52,375 questions
60,554 answers
95,374 users