Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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!

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Wikipedia is confusing the issue by bringing in perfect matchings. Think of a matching as a "packing" of edges into a graph, so no two have a vertex in common. Clearly the maximum size of a packing is less than or equal to the minimum size of a cover. (This works for packing triangles, or paths of fixed length, or...)

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.

Note that the minimum size of a vertex cover is at least as large as the size of a maximum matching (because the cover must contain at least one vertex from each matching edge). And the minimum size of an edge cover is at least as large as the maximum size of an independent set.

share|improve this answer
    
Thanks! (1) "Clearly the maximum size of a packing is less than or equal to the minimum size of a cover." I wonder why? (2) "in the first paragraph the packings are vertex-disjoint", do you mean a matching is vertex-disjoint? "in the second they are disjoint", means an independent set is disjoint?(3) "The situation with independent sets and vertex cover is analogous." Do you mean that the size of a maximum independent set is no bigger than the size of a minimum vertex cover? However a graph without edges is a counterexample. –  Tim Oct 30 '12 at 13:26
    
(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
    
For (3), in my comment, for example, a star has no isolated vertex, and its independent set and vertex cover can vary from size 1 to total vertex number minus 1. –  Tim Oct 31 '12 at 1:44
    
Yes, I made a mess of that. I've edited my answer. –  Chris Godsil Oct 31 '12 at 3:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.