Hall's Marriage Theorem $2n$ Rooks on $2n \times 2n$ board I saw this question on https://brilliant.org/wiki/applications-of-hall-marriage-theorem/. I can't work it out, any help would be appreciated!

In a $2n \times 2n$ chess board, there are $n$ rooks in each row and each column of the board. Show that there exist $2n$ rooks that belong to pairwise distinct rows and pairwise distinct columns.


Consider the bipartite graph in which the first set of vertices is the set of rows, the second set of vertices is the set of columns, and there is an edge between a row and a column if and only if the square corresponding to that row and column has a rook in it.
We must verify that this graph satisphies the Hall condition.
So take a set of $k$ rows, we must show that the rooks on these rows cover at least $k$ columns.
Assume this is not the case, then clearly $k$ is greater than $n$ (because each row has $n$ rooks). But if $k>n$ it is also impossible, because each column has to contain at least one rook in one of the rows ! (because otherwise each column would have at most $n-k$ rooks, which is less than $n$).
Hence this graph satifies the Hall condition, and thus has a perfect matching, which translates into precisely what we want.
