# Homework 11

Due Monday, March 2 at 5:00 PM. Please refer to the homework policy here.

## Problems

1. Problem 3 in Chapter G of Jeff's notes. (Every year, Professor Dumbledore...)
2. Let $G = (V,E)$ be an undirected graph. Prove that there is (always) a pair of nodes $s,t \in V$ such that either $(\{s\}, V \setminus \{s\})$ or $(\{t\}, V \setminus t)$ is the minimum $\{s,t\}$ cut.