From Wikipedia:
A perfect matching is also a minimum-size edge cover. Thus, the size of a maximum matching is no larger than the size of a minimum edge cover.
I know that a perfect matching is a maximum and hence maximal matching. But I don't understand why "the size of a maximum matching is no larger than the size of a minimum edge cover"?
- Is the size of any matching no larger than the size of any edge cover? If Part 1 is true, then I think part one implies this part?
Similar questions for independent sets and vertex covers.
I understand that the complement of an independent set is a vertex cover, and the complement of a vertex cover is an independent set.
Is there a definite answer to which is no greater than which, the size of a maximum independent set and the size of a minimum vertex cover?
Similar question for the size of any independent set and the size of any vertex cover?
Thanks!