# Relation between sizes of matching, edge cover, independent set and vertex cover

1. 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"?

2. 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?
3. 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!

-

For vertex covers and independent sets, the complete bipartite graph $K_{1,3}$ has a vertex cover of size 1 and an independent set of size 3. The cycle $C_5$ has an independent set of size 2, but any vertex cover has size at least three. So there is no simple relation between the minimum size of a vertex cover and the maximum size of an independent set.
(1) If we have a matching $M$ of maximum possible size $m$ ($m$ edges), then it covers $2m$ vertices. If $C$ is a cover, then it must cover all $2m$ vertices covered by $M$, and therefore $C$ must contain at least $m$ edges. So $|M|\le|C|$. (2) I mean that the edges in a matching are vertex disjoint. (3) If we are going to discuss edge covers, we need to assume that each vertex is in an edge. – Chris Godsil Oct 30 '12 at 19:50