Min-Cut Theorem and Bipartite Matching

A story: assigning projects without wasting a student's skills

A university career centre has three students and two industry projects. Each student has a different set of skills: A can work on X, B can work on X or Y, and C can work on Y. The coordinator wants as many students as possible to receive a project, but no project can take two students. This is not merely a matter of greedily assigning the first student to the first project. A locally reasonable choice can block a better overall assignment.

The same problem appears in course registration, hospital shift allocation, job matching, network bandwidth, and production scheduling. Maximum flow provides one common mathematical model for these problems. The min-cut theorem then gives a certificate that the computed answer is optimal, while bipartite matching turns the same machinery into a way to allocate people to eligible tasks.

Learning outcomes

By the end, you should be able to:

• Model a capacity-constrained network with a directed graph.
• Explain residual capacity, augmenting paths, bottlenecks, and reverse edges.
• Compute a maximum flow on a small network by hand.
• Use the max-flow/min-cut theorem to prove an upper bound is tight.
• Reduce bipartite matching to a maximum-flow problem and interpret the result.

1. The network model

Represent a network as a directed graph G=(V,E). Each edge (u,v) has a non-negative capacity c(u,v), such as 3 units of bandwidth or three available seats. A source s supplies flow and a sink t receives it. A valid flow f must obey three rules:

1. Capacity: 0 ≤ f(u,v) ≤ c(u,v). An edge cannot carry more than its capacity.
2. Conservation: for every vertex other than s and t, incoming flow equals outgoing flow. A router cannot create bandwidth from nowhere.
3. Value: the flow value is the total flow leaving the source, equivalently the total flow entering the sink.

The objective is to maximise the flow value. Unlike shortest-path problems, the aim is not to find one cheapest route. Several routes may share the work, and the capacities of shared edges can limit the total.

2. Worked example: route five units through a network

Consider the following directed network. The number on each edge is its capacity.

Start with zero flow. An augmenting path is a source-to-sink path with positive residual capacity on every edge. Its bottleneck is the smallest residual capacity along that path. Sending more than the bottleneck would violate at least one edge capacity.

Augmentation 1: S → A → T

The capacities are 3 and 2, so the bottleneck is min(3,2)=2. Send two units. The edge S → A has one unit left, while A → T is now full.

Augmentation 2: S → B → T

The capacities are 2 and 3, so the bottleneck is 2. Send two more units. S → B is now full and B → T has one unit of capacity left. The total flow is 4.

Augmentation 3: S → A → B → T

A → T is full, but the route through B remains possible. S → A has one unit left, A → B has capacity 1, and B → T has one unit left. Send one unit. The total flow is now 5.

No more flow can leave S because both outgoing source edges are saturated. The computed flow is 5.

3. Residual networks: why reverse edges matter

A residual network records how much more flow can be sent and how much previous flow can be cancelled. For a forward edge, residual capacity is c(u,v)-f(u,v). A reverse residual edge carries capacity f(u,v): it represents the option to undo some earlier routing decision.

This is crucial for matching. Suppose B is initially assigned to project X, leaving A with no project. A later augmenting path can traverse a reverse edge to undo B → X, then reroute B to Y and assign A to X. The algorithm is not trapped by its first assignment. Reverse edges do not mean the original network suddenly allows a physical reverse transfer; they are bookkeeping that lets the algorithm revise a previous flow.

Breadth-first search can find an augmenting path with the fewest edges. Repeating this procedure is the Edmonds–Karp algorithm. If no augmenting path remains, the current flow is maximum.

4. From maximum flow to a proof: the min-cut theorem

A cut divides the vertices into two sets S and T, with the source in S and sink in T. Its capacity is the sum of capacities of all original edges directed from the source side to the sink side: C(S,T) = sum of c(u,v) for edges from S to T.

Any unit of flow reaching the sink must cross the cut, so no flow can exceed the cut capacity. In our example, choose S= and T=. The only outgoing cut edges are S → A with capacity 3 and S → B with capacity 2. The cut capacity is 3+2=5.

We found a feasible flow of 5 and a cut of capacity 5. Since every flow is at most every cut, the optimum must be exactly 5. This is a certificate of optimality: the flow proves at least 5 is possible; the cut proves more than 5 is impossible. The max-flow/min-cut theorem states that the maximum flow value equals the minimum cut capacity.

5. Bipartite matching as a flow problem

A bipartite graph has two disjoint sets of vertices, such as students and projects, and edges only between the sets. To find the largest one-to-one assignment:

1. Add a source and an edge of capacity 1 from the source to each student.
2. For each eligible student–project pair, add an edge of capacity 1.
3. Add an edge of capacity 1 from each project to the sink.
4. Compute maximum flow. Every unit of flow corresponds to one student assigned to one eligible project.

For the opening story, add edges A → X, B → X, B → Y, and C → Y. The maximum matching has size 2 because only two projects exist. One valid assignment is A → X and C → Y; B remains unassigned. The algorithm can also find B → X and C → Y. If a first choice blocks an additional assignment, residual reverse edges allow reassignment rather than accepting a smaller result.

6. A reproducible Python implementation

The following Edmonds–Karp implementation stores residual capacities in adjacency dictionaries. Reverse edges are created explicitly, and breadth-first search only follows positive residual capacity.

from collections import defaultdict, deque

def edmonds_karp(edges, source, sink):
    residual = defaultdict(dict)

    for u, v, capacity in edges:
        if capacity < 0:
            raise ValueError("Capacities must be non-negative")
        residual[u][v] = residual[u].get(v, 0) + capacity
        residual[v].setdefault(u, 0)

    total_flow = 0

    while True:
        parent = {source: None}
        queue = deque([source])

        while queue and sink not in parent:
            u = queue.popleft()
            for v, available in residual[u].items():
                if available > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)

        if sink not in parent:
            break

        bottleneck = float("inf")
        v = sink
        while parent[v] is not None:
            u = parent[v]
            bottleneck = min(bottleneck, residual[u][v])
            v = u

        v = sink
        while parent[v] is not None:
            u = parent[v]
            residual[u][v] -= bottleneck
            residual[v][u] = residual[v].get(u, 0) + bottleneck
            v = u

        total_flow += bottleneck

    return total_flow, residual

edges = [
    ("S", "A", 3), ("S", "B", 2), ("A", "B", 1),
    ("A", "T", 2), ("B", "T", 3),
]
value, residual = edmonds_karp(edges, "S", "T")
print(value)  # 5

The code rejects negative capacities, searches only edges with positive residual capacity, and updates both the forward and reverse residual capacities. For adjacency-list implementations, Edmonds–Karp runs in O(VE²) time; the residual graph requires O(V+E) space. For large sparse networks, a specialised implementation such as Dinic's algorithm may be faster.

7. Common mistakes and trade-offs

• Confusing a path with the whole solution: the best total may combine multiple paths.
• Ignoring residual reverse edges: this can prevent the algorithm from revising a poor earlier routing choice.
• Using a greedy assignment without proof: choosing the first eligible project does not guarantee maximum matching.
• Mixing a cut with an undirected edge sum: only original directed edges leaving the source side count toward cut capacity.
• Assuming all algorithms have the same performance: Edmonds–Karp is conceptually clear and useful for teaching, while Dinic or specialised matching algorithms can be preferable for larger instances.

Practice lab

1. Change the capacity of S → A from 3 to 1. Predict the maximum flow before running the code, then calculate the new minimum cut.
2. Remove the edge A → B. Can the network still send five units? Explain why.
3. Build the bipartite graph with students A, B, C and projects X, Y. List all eligible edges and find a maximum matching.
4. Draw one residual reverse edge after the first augmentation and explain which previous decision it can undo.
5. Give one situation where a maximum flow is a better model than a shortest path, and state the capacity represented by each edge.

Model answers

1. The source can send at most 1+2=3 units, so the maximum is 3.
2. No. The direct routes S → A → T and S → B → T can carry 2+2=4 units only, so the maximum becomes 4.
3. A matching of size 2 exists, for example A → X and C → Y. A matching of size 3 is impossible because there are only two projects.
4. After sending flow on an edge such as S → A, its reverse residual edge A → S records how much of that flow could be cancelled if a later augmenting path needs to revise the routing.
5. A network bandwidth allocation problem is a flow problem because several routes share finite link capacities. A shortest-path problem instead seeks one route that minimises a path cost.

Further reading and source notes

• Princeton Algorithms: Maximum Flow and Minimum Cut, residual networks, flow feasibility, and cut certificates.
• CP-Algorithms: Edmonds–Karp, augmenting-path implementation and complexity.
• Princeton Algorithms: Bipartite Matching, reductions and matching-related applications.

Use the graph and edge capacities from this lesson to reproduce the calculations before relying on the code. For an assessed implementation, add tests for zero capacity, disconnected sink, multiple eligible assignments, and an invalid negative capacity.