My approach is to construct a network on the bipartite graph, with the source and sink being two extra vertices, each adjacent to all vertices from one partition of G. All edges are "forward" edges, with capacity 1.
I'm getting stuck at the part where I have to show $\alpha'(G) \geq \beta(G)$, specifically where I have to relate $\beta(G)$ to min cap(S,T). How are source/sink cuts related to the vertex cover number? I would like some hints if possible. Thanks.
Best Answer
To get a bound on the vertex cover, it's easiest to use different capacities. Put capacity $\infty$ on the edges of the bipartite graph; put capacity $1$ on the edges out of $s$ or into $t$.
Then we can guarantee that the edges crossing any minimum $s,t$-cut only consist of the capacity $1$ edges. (If there is a single capacity-$\infty$ edge, then the capacity of the cut is $\infty$ as well. But there is definitely a cut with finite capacity: for example, the cut with one side only $\{s\}$.)
Such edges are in one-to-one correspondence with vertices of the graph, and the edges crossing a minimum $s,t$-cut will correspond to a minimum vertex cover.
If a capacity of $\infty$ bothers you, you can simply use any value larger than the number of vertices in the graph, for example. In fact, I'm pretty sure capacity $1$ still works; we just have to do more work arguing that there are minimum cuts whose only crossing edges are edges out of $s$ or into $t$.