Maximum Matching - Walkthrough

Trace an example: $4$ vertices in $L$, $3$ in $R$, edges $\{(1,1), (2,1), (2,2), (3,2), (4,3)\}$. Try matching $1$ to $1$, $2$ to $2$, then $3$ needs to bump someone. DFS finds an augmenting path. $4$ matches to $3$. Final matching: size $3$.

Notice how DFS automatically finds augmenting paths when a direct match fails. This is the power of the recursive approach. The algorithm handles complex rematching without explicit path tracking.