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