1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.