CSDS 455: Applied Graph Theory
Homework 16
Our subject next week is flows. We will spend much of the time looking at k-flows, but for this weekend, I
want to read about (or recall) network flows where we have a source and a sink on a graph.
Problem 1: Prove that you can reduce the maximum bipartite matching problem to the network flow
problem. (Given a bipartite graph, turn it into a flow problem such that the value of the flow equals the
maximum matching of the bipartite graph.)
Problem 2: Prove that you can reduce Menger’s Theorem to the network flow problem. (Given a graph,
turn it into a flow problem so that the flow size gives the number of vertex disjoint paths of the graph.)
Problem 3: Suppose we have a network (directed graph) D with edge weights (capacities) and with source
node s and sink node t. Let S ⊂ V (D) and T ⊂ V (D) be subsets of nodes such that s ∈ S, T but t /∈ S, T.
(S, S) is a cut of the network, and cap(S, S) is the sum of weights of edges with their tail in S and head in
S. Prove that cap(S ∪ T, S ∪ T) + cap(S ∩ T, S ∩ T) ≤ cap(S, S) + cap(T, T).
