Hall's marriage theorem and regular bipartite graphs

1. ($\Rightarrow$) is clear: the $|S|$ partners of the vertices of $S$ are distinct elements of $N(S)$.

($\Leftarrow$) Induction on $|A|$; the case $|A|=1$ is clear. Assume Hall's condition.

*Case 1: $|N(S)|\ge|S|+1$ for every nonempty proper $S\subset A$.* Pick any $a\in A$ and any neighbour $b$ of $a$. Remove $a$ and $b$. For every nonempty $S\subseteq A\setminus\{a\}$, removing $b$ lowers the neighbourhood by at most $1$, so $|N'(S)|\ge|N(S)|-1\ge|S|$. By induction $A\setminus\{a\}$ can be matched, and we add the pair $\{a,b\}$.

*Case 2: some nonempty proper $S$ has $|N(S)|=|S|$.* The graph induced on $S\cup N(S)$ satisfies Hall's condition, so by induction $S$ is matched onto $N(S)$. In the rest of the graph,
$$|N(T)\setminus N(S)|=|N(T\cup S)|-|N(S)|\ge|T|+|S|-|S|=|T|.$$
So Hall's condition holds there and, by induction, $A\setminus S$ is matched. The two matchings together match $A$.

2. Counting edges, $k|A|=k|B|$, so $|A|=|B|$. For $S\subseteq A$, there are $k|S|$ edges leaving $S$, and they all end in $N(S)$, where each vertex receives at most $k$ of them. So $k|N(S)|\ge k|S|$. By Hall, $A$ is matched into $B$, and since $|A|=|B|$ this matching is perfect.

3. Let $A$ be the set of $13$ piles, $B$ the set of $13$ ranks. This is a $4$-regular bipartite multigraph. A perfect matching is exactly the required choice.

Lesson. To prove a matching exists, check Hall's condition; for regular graphs, double count edges.