The Gateway to Computer Science Excellence
0 votes
The size of minimum vertex cover can be -

 (A) Smaller than the size of maximum matching

 (B) No smaller than the size of maximum matching

 (C) Cannot say
in Revision by | 62 views

1 Answer

0 votes

Let G=(V,E)G=(V,E) be a graph, let M⊆E(G)M⊆E(G) be a maximum matching of the graph GG, and let C⊆V(G)C⊆V(G) be the minimum vertex cover of GG. Since edges in MM are disjoint in the sense that no two share an endpoint, each vertex in v∈Cv∈C covers at most one edge in MM. Thus |C|≥|M||C|≥|M|.


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,345 questions
60,471 answers
95,273 users