[Math] Relation between sizes of matching, edge cover, independent set and vertex cover

graph theory

  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!

Best Answer

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.

Related Question