School Dance - Walkthrough

we trace an example: $3$ boys, $3$ girls, edges $\{(1,1), (1,2), (2,2), (3,3)\}$. Start with boy $1$, match him to girl $1$. Boy $2$ matches to girl $2$. Boy $3$ matches to girl $3$. Matching size = $3$. This is a perfect matching. Now try $\{(1,1), (2,1)\}$.

Boy $1$ matches girl $1$. Boy $2$ tries girl $1$, she's taken. DFS tries to rematch boy $1$, but he has no other options. The attempt fails. Final matching size = $1$. This shows why some graphs have smaller matchings.