The Gateway to Computer Science Excellence
0 votes
51 views
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 (21 points) | 51 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|.

https://math.stackexchange.com/questions/507605/the-size-of-the-maximum-matching-is-bounded-by-the-size-of-the-minimum-vertex-co

by Active (3.8k points)

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,508 answers
195,518 comments
100,941 users