Show that $G$ satisfies Hall's condition

Question

Show that $G$ satisfies Hall's condition

I knew the definition:

Let $G$ be a bipartite graph with partite sets $U$ and $W$, where $r=|U|\leq|W|$. Then $G$ satisfies Hall's condition if, for every $S\subseteq U$, $|S|\leq|N(S)|$.

But did I need to check it for all subsets manually to answer that question? Because I easily found a perfect match. And Hall condition implies the existence of a perfect match, but I don't know the reverse is true or not? Then how to deal with this question without huge amount of checking?

Answer 1

And Hall's condition implies the existence of a perfect match, but I don't know the reverse is true or not?

Suppose that you found a perfect match but that Hall's condition were not satisfied. Then there would exist some $S \subseteq U$ for which $|S| > |N(S)|$. It would be impossible to match all the elements of $S$, a contradiction.

In other words, if you found a perfect match, then you are done.

Answer 2

Well, one direction of Hall's Theorem is easy to see: If a bipartite graph $G$ has a perfect matching, then $G$ satisfies Hall's Condition. [The other direction: If $G$ satisfies Hall's Condition, then $G$ has a perfect matching, is the harder direction to see.] However here $G$ does have a perfect matching $M$; in fact $M$ is as follows: $M=\{1a, 2c,3b,4d,5f,6e\}$.