# Is Hall's theorem just about subsets?

Hall's theorem says that in a bipartite graph with parts $V_0+V_1$, there's a matching of $V_0$ if and only if $U\subset V_0\implies |U|\leq N_G(U)$. Isn't "a matching of $V_0$" the same as saying an injection $V_0\rightarrow V_1$?

Is Hall's theorem just characterizing when there's an injection between finite sets?

• I think you might have Hall's theorem slightly wrong. What does "edges $V_0+V_1"$ mean? Hall's theorem holds for any bipartite graph. – Mosquite Sep 16 '16 at 20:28
• @Mosquite I mean the bipartite graph has parts $V_0,V_1$. – combinarcotics Sep 16 '16 at 20:32
• A matching is not just an injection because it also require edges to exist in the graph. An injection from $V_0 \to V_1$ is a necessary condition for a matching but not sufficient. Consider a bipartite graph with no edges; it has no matching. I will turn this into an answer. – Mosquite Sep 16 '16 at 20:35

A matching is not just an injection because it also require edges to exist in the graph. An injection from $V_0 \to V_1$ is a necessary condition for a matching but not sufficient. Consider a bipartite graph with $|V_0| = 1$ and $|V_1| = 2$ and no edges; it has no matching, but there is definitely an injection from $V_0$ to $V_1$.
However, a matching induces an injection between $V_0$ and $V_1$. Also, if we take two sets $V_0$ and $V_1$ there exists an injection from $V_0$ to $V_1$ if and only if there is a matching in the complete bipartite graph with parts $V_0$ and $V_1$ that covers $V_0$.
Finally, Hall's theorem more explicitly says "there's a matching that covers $V_0$".
Hall's theorem is not about whether there is an injection between finite sets. This is because that the matched pairs in a "matching of $V_0$" must be adjacent (connected by an edge) in the graph. So Hall's theorem is a much more interesting statement.
If you want to think about it in terms of injectivity, Suppose we are given a relation $\boldsymbol{R}$ (the edge relation), between the finite set $V_0$ and the finite set $V_1$. Hall's theorem gives the necessary and sufficient condition under which this relation has a subset which is an injection $V_0 \to V_1$.
If you apply Hall's theorem in the specific case where the relation is $V_0 \times V_1$ (every pair of $V_0$ and $V_1$ is connected by an edge), then you get that there is an injection $V_0 \to V_1$ iff $|V_0| \le |V_1|$. But Hall's theorem is much more general than this.