School Dance - Walkthrough

Example: $3$ boys, $3$ girls. Boy $1$ likes girls $1$ and $2$. Boy $2$ likes girl $2$. Boy $3$ likes girl $3$. Build the flow graph with source, boys, girls, and sink. All edges have capacity $1$. Max flow is $3$, meaning all boys can be paired. Edmonds-Karp finds augmenting paths:

$1.$ $s \to \text{boy}_1 \to \text{girl}_1 \to t$ (bottleneck $1$).

$2.$ $s \to \text{boy}_2 \to \text{girl}_2 \to t$ (bottleneck $1$).

$3.$ $s \to \text{boy}_3 \to \text{girl}_3 \to t$ (bottleneck $1$).

Final pairs: ($1$,$1$), ($2$,$2$), ($3$,$3$). Output $3$ pairs. The algorithm found a perfect matching where everyone dances.