Showing a perfect match in bipartite graph Let G be a bipartite graph with partite sets U and W such that $|U|=|W|=r \ge 1$
Suppose that $U={{u_1,u_2,..,u_r}}$ and $W={w_1,w_2,...,w_r}$. Two vertices $u_i$ and $w_j$ are adjacent in G if and only if $i+j \ge r+1$. Show that G has a perfect matching 
Apparently I have to use the following theorem to show its perfect matching.

For a bipartite graph G with partite sets U and W and for $S \subset U$ let $N(S)$ be the set of all verticies in W having a neighbor in S . The condition that
$$|N(S)|\ge |S|$$ for all $S \subset U$ is reffered to Hall condition.
Theorem 12.3
Let G be a bipartite graph with partite sets U and W. Then U can be matched to a subset of W if and only if the hall condition is satisited.
But I am kind of lost.

You can actually manage without Hall's marriage theorem, just by exhibiting a perfect matching (actually the only one, I think):


*

*Match $u_i$ to $w_{r-i+1}$


But if determined to  use the theorem, you can note that any group of $n$ nodes from $U$ will be linked to at least $n$ nodes in $W$ because the maximum index number in the $U$ subset, $u_m$, must have $ m \ge n$, and this node is linked to $m$ nodes from $w_r$ down to $w_{r-m+1}$ - that is, at least $n$ nodes.
