How to prove that 3-CNF is satisfiable using Hall's marriage theorem? 
Given a 3-CNF formula where each variable from variables $x_1,...,x_n$ appears exactly 3 times in different clauses $c_1,...,c_m$, and each clause contains exactly 3 different variables, prove that the formula is satisfiable using Hall's marriage theorem.

Firstly, because each variable appears in 3 different clauses and each clause contains 3 different variables it follows that $n=m$.
We can define $X=\{x_1,...,x_n\}$, $Y=\{c_1,...,c_n\}$ and a bipartite graph $G=(X\cup Y, E)$ where $E=\{(x_i, c_j)|x_i\in c_j\}$.
Let $P$ be a set of clauses, $P \subseteq Y$.
In order to use Hall's theorem I need to prove that $|\Gamma(P)|\ge |P|$, where $|\Gamma(P)|$ means the neighborhood of $P$ (all adjacent vertices)  but I'm really not sure how to prove that using graph theoretic formulation of Hall's theorem.
 A: You've already set the problem up, and the rest is a classic corollary of Hall's theorem:

Every $k$-regular bipartite graph has a perfect matching.

In case you are unfamiliar: here $k$-regular means that the degree of each vertex is $k$ and a perfect matching is a collection of disjoint edges that covers all the vertices. You have a $3$-regular bipartite graph, and a perfect matching would assign to each clause a unique variable, which you would then set to be true or false to make that clause true.
Proof: Let $P \subseteq Y$. Since the degree of each vertex of $P$ is $k$, there are $|P|\cdot k$ many edges between $P$ and $\Gamma(P)$. But since the degree of each vertex of $\Gamma(P)$ is $k$ and $P \subseteq \Gamma(\Gamma(P))$, there are at most $|\Gamma(P)|\cdot k$ many edges between $P$ and $\Gamma(P)$. This implies that $|P|\cdot k \leq |\Gamma(P)| \cdot k$, or $|P| \leq |\Gamma(P)|$ as desired.
Note that we can apply this result repeatedly: a $k$-regular bipartite graph minus a perfect matching is a $(k-1)$-regular bipartite graph. Thus we can partition the edges of a $k$-regular bipartite graph into $k$ perfect matchings (this is known as a 1-factorization). This means that there are at least 3 ways your 3-CNF is satisfiable!
