0 votes 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 Graph Theory vertex-cover + – ashutoshsharma asked Sep 21, 2017 ashutoshsharma 395 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 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 Arpit Dhuriya answered Dec 6, 2017 Arpit Dhuriya comment Share Follow See all 0 reply Please log in or register to add a comment.