Intuition behind Hall's theorem. I have chosen combinatorics as my elective in my $3^{\text{rd}}$ semester.There is a theorem in combinatorics known as Hall's marriage problem.Let us first define some terminologies:

Defn. A system of distinct representatives for a sequence of sets $S_1,S_2,...,S_m$(not necessarily distinct) is a sequence of distinct elements $x_1,...,x_m$ such that $x_i\in S_i$ for all $1\leq i\leq m$.

Now the statement of Hall's theorem is as follows:

Th. The sets $S_1,S_2,...,S_m$ have a sequence of distinct representatives if and only if for every $I\subset \{1,2,...,m\}$,$|\bigcup\limits_{i\in I} S_i|\geq |I|$.

But I find this theorem hard to remeber because I don't understand what it really means.I have searched on internet but there it is something a bit different and explained using graph theory which I have not studied yet.So,I am looking for intuition behind this theorem.Can someone explain with a suitable example?
 A: This problem is indeed best explained in the context of graph theory, and that's what I'm going to do! But since you don't know any graph theory, let's start simple by using our intuition.
First, let's look at an example of your theorem. Say $m = 3$, and we have $3$ sets: $S_1 = \{a, b\}$, $S_2 = \{b, c\}$ and $S_3 = \{a, d, e\}$. Then if you think about this more closely, this can be thought of as a function. Indeed, we can think of it as a function $s: \{1, 2, 3\} \to \{a, b, c, d, e\}$, where $s(1) = \{a, b\}$, etc. If you recall from high school, we can draw functions as arrows between sets! categorists shivering Here is a picture of it.

This picture of "edges connecting some nodes" is what we call a graph. Easy right! Actually here we have an additional property: all edges connect from the left ($\{1, 2, 3\}$) to the right ($\{a, b, c, d, e\}$). This property is of course by construction of the function, and when we can split a graph's nodes into two sets such that all edges connect the two sets, we call the graph bipartite. This is probably what you will read if you google "Hall's Theorem" online.

Now let's look at the theorem statement itself. (Combining your two definitions) It says that given the sets $S_1, S_2, \ldots, S_m$, we can find $m$ distinct elements $x_1, x_2, \ldots, x_m$, each of which lies inside its parent set, if and only if for any $I \subset \{1, 2, \ldots, m\}$, $\left|\bigcup_{i \in I} S_i\right| \geq |I|$. Let's break it down into a few parts.
Firstly, what does it mean to find the distinct representatives? In our example, we need to pick one element from each of the sets $S_1, S_2, S_3$ which are distinct. In the graph picture, it is the same as picking one of the edge from each of the node on the left, such that the connected node on the right are all distinct. For example, the green representatives are okay, since $(x_1, x_2, x_3) = (b, c, d)$, while the red representatives are not. In other words, for each node on the left we are matching an element from the right, hence the wording of "bipartite matching" you might have come across.

And now with this picture of matching in mind, let's think under what conditions can we find such a matching - actually, let's think about under what conditions can we not find a matching. Well, say $S_1 = \{a, b\}$, $S_2 = \{\}$ and $S_3 = \{c\}$. $S_2$ is empty (so the node $2$ has no outgoing edges), and hence it is impossible. Another less trivial case would be if $S_1 = \{a, b\}$, $S_2 = \{a\}, S_3 = \{c\}$ and $S_4 = \{b\}$. Here, it is still impossble. This is because if we only look at $S_1, S_2, S_4$, we see that they all connect to $\{a, b\}$ only. In other words, $S_1 \cup S_2 \cup S_4 = \{a, b\}$, and obviously we cannot choose three unique representatives from two elements. And we have found our observation: in general, if any $k$ sets of the $m$ sets together (union) share less than $k$ elements, then it's impossible to find a matching!

With this, we can finally write the condition down symbolically, as $\left|\bigcup_{i \in I} S_i\right| \geq |I|$ for all $I \subset \{1, 2, \ldots, m\}$. Note that so far, we have only proven (or intuitively seen) half of the theorem, i.e. the "representatives $\implies$ " direction by taking contrapositive. However, Hall's Theorem tells you that the opposite direction holds as well: if every union of $k$ sets has at least $k$ elements, then you can always find some representatives. As usual in mathematics, that's the direction that's harder to prove.
Hope it helps and introduced you to some graph theory!
A: Let me try and give an intuitive example. In your school there are $m$ different clubs: a sports club, chess club, math club, music club, etc. These correspond to the $m$ sets $S_1, \cdots, S_m$. The clubs are not independent because some people are in multiple clubs. The principal wants to meet with members of each club, so a representative must be chosen for each club. In addition, the principal insists that a single person cannot represent two clubs -- if you belong to both the math and music club, you can represent at most one. The question is -- is this possible?
Suppose that me and two friends got bored and decided to make four clubs just for us, based on our various niche interests. This will cause a problem, as we are three people and we cannot represent four clubs. Let's denote our four clubs $S_1, S_2, S_3, S_4$. This problem of having only three people represent four clubs can be written as $|\bigcup_{i=1}^{4}S_i| = 3 < 4$. In general, for any collection of clubs $I \subset \{1, \cdots, m\}$, if we find out that these clubs have fewer than $|I|$ people in total, we will end up with too few representatives, and again we will be stuck. Mathematically, this is $|\bigcup_{I}S_i| < |I|$. This proves half of the theorem: if $|\bigcup_{I}S_i| < |I|$, then certainly we cannot find enough representatives.
The theorem says that this is the only obstruction to finding enough representatives. As long as you can be sure that $|\bigcup_{I}S_i| < |I|$ never happens, you can find distinct representatives for each club. This is a common kind of result in math -- you identify an "obvious" obstruction to something happening, and then you prove that this is the only possible obstruction, giving a sufficient and necessary condition.
