Vertex cover in bipartite graph

Task number: 3995

The vertex cover of a graph \( G = (V, E) \) is a set \( U \subseteq V \), which has at least one common vertex with each edge of the graph.

Prove that in any bipartite graph, the size of the smallest vertex cover is equal to the size of the largest matching.

  • Hint

    Use duality between flows and cuts in an appropriate network.

  • Solution

    We convert the bipartite graph with classes of bipartition \( A, B \) to the network with unit capacities by connecting a source \( s \) with edges to all vertices from the set \( A \), similarly \( B \) to the target \( t \), and all edges go from \( A \) to \( B \).

    We find the maximum flow, and because the edge capacities are integers, you can choose an integer maximum flow. The flow edges used between parts \( A \) and \( B \) form the matching, because no vertex of \( A \) can saturate two edges: There are unit capacities on edges towards \( A \). Similarly for the vertices of \( B \). This is the maximum matching because each matching can be converted to a flow.

    If we have an edge cut \( F \), it can be assumed without loss of generality that each edge of the cut is incident with \( s \) or with \( t \): Otherwise we replace the edge of the cut between \( A \) and \( B \) with its successor leading to \( t \). For \( U \) we choose those vertices from the set \( A \cup B \), which belong to the edges of the cut \( F \). Evidently \(|U|=|F|\). In addition, the set \( U \) is a vertex cover of the original bipartite graph. An uncovered edge would correspond to a saturating path between \( s \) and \( t \), and thus \( F \) would not be a cut.

    Similarly, a cut of the same capacity can be created from each vertex cover \( U \).

    Hence, the size of the minimum vertex cover is equal to the capacity of the minimum cut, and this is equal to the sizes of the maximum flow and the maximum matching.

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email