DISCRETE

Question

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

Answer 1

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