Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
  1. From Wikipedia, in a bipartite graph, when given a maximum matching, there is way to construct a vertex cover of the same size as the matching:

    Consider a bipartite graph where the vertices are partitioned into left (L) and right (R) sets. Suppose there is a maximum matching which partitions the edges into those used in the matching ($E_m$) and those not ($E_0$). Let T consist of all unmatched vertices from L, as well as all vertices reachable from those by going left-to-right along edges from $E_0$ and right-to-left along edges from $E_m$. This essentially means that for each unmatched vertex in L, we add into T all vertices that occur in a path alternating between edges from $E_0$ and $E_m$.

    Then $(L \setminus T) \cup (R \cap T)$ is a minimum vertex cover. Intuitively, vertices in T are added if they are in R and subtracted if they are in L to obtain the minimum vertex cover. Thus, the Hopcroft–Karp algorithm for finding maximum matchings in bipartite graphs may also be used to solve the vertex cover problem efficiently in these graphs.

    I am not sure how $T$ is constructed, and cannot picture $T$ even after reading the sentences in bold. So I wonder how to understand those sentences?

  2. Conversely, in a bipartite graph, when given a minimum vertex cover, what is some way to construct a matching of the same size as the vertex cover?


PS: This is from my comment on Fixee's reply.

share|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.