• Overview
• Details
• Exercises

Connectivity measures robustness of graphs to vertex/edge removal. Cuts separate graphs into parts and underpin min-cut problems. Flows route quantities through networks; max-flow min-cut duality connects the two.

• Connectivity: k-edge- and k-vertex-connectivity; components; bridges and articulation points.
• Cuts: (S, V\S) in undirected; s–t cut capacity is sum of capacities crossing from S to V\S.
• Flows: feasible flows satisfy capacity and conservation constraints; value is net outflow at source.
• Max-flow min-cut theorem: maximum s–t flow value equals minimum s–t cut capacity.
• Algorithms: Ford–Fulkerson/Edmonds–Karp (augmenting paths), Dinic (blocking flows), Push–Relabel.
• Applications: routing, bipartite matching, image segmentation, project selection, connectivity augmentation.

1. Find all bridges and articulation points in a given graph (Tarjan-style DFS).
2. Compute a max flow and a minimum s–t cut on a small network; verify equality.
3. Reduce bipartite matching to max flow and solve a sample instance.