# 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.

• 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.