Marginalia on Hall's marriage theorem (a) Let $G=( X \cup Y, E)$ be a connected bipartite graph. Show that every edge of $G$ extends to a matching from $X$ and $Y$ if and only if for all $A \subseteq X$,$A\neq \emptyset ,X$, we have $\left|N_G (A)\right| \gt \left|A\right|$. 
(b) Let $K=( X \cup Y, E)$ be a infinite bipartite graph satisfying Hall's condition (that is, $\left|N_G(A)\right| \geq \left|A\right|$ for every $A \subset X$). Show that it does not necessarily contain a matching from $X$ to $Y$.
For part (a), I tried to do the $(\Rightarrow)$ part (not sure it's correct or not) but I couldn't do the $(\Leftarrow)$ part. I know it should be similar to the prove of Hall’s marriage theorem by induction. Below is my answer for $(\Rightarrow)$.
As $G$ extends to a matching from $X$ to $Y$, then all the vertices must have degree $\gt$ 1, therefore it implies that $|N_G (A)| \gt |A|$ for all $A \subset X$.
And for part(b), I have totally no clue how to start it. Could anyone teach me how to do it please?
 A: $(a, \Longleftarrow)$ Suppose that you have $|N(A)| > |A|$ for any $A \subseteq X$ such that $A \neq \varnothing$ and $A \neq X$. Now, pick any edge $e$ and remove it from the graph, together with its endpoints. Let's call this new graph $G' = (X' \cup Y', E')$. Observe that for any $A' \subseteq X'$ we have $$|N_{G'}(A')| \geq |N_G(A')| -1 > |A'| - 1,$$
which implies $|N_{G'}(A')| \geq |A'|$. Thus, we know that there exists an $X'$-saturating matching in $G'$, and by adding the edge $e$ back again, we obtain that there is an $X$-saturating matching using $e$.
$(a, \Longrightarrow)$ Let $A$ be a minimal (with regard to inclusion) non-empty set such that $|N(A)| = |A|$, we will show that either $A = X$ or there exists an edge $e$, which does not belong to any $X$-saturating matching in $G$.
Let $V_1 = A \cup N(A)$ and $V_2 = V \setminus V_2$. Because the graph is connected, if $V_1 \neq V$, then there has to be an edge between $V_1$ and $V_2$, we will call it $e$. As any edge that starts in $A$ ends, by definition, in $N(A) \subseteq V_1$, hence, $e$ has to go from $N(A) = V_1 \cap Y$ to $V_2 \cap X$. But then, $e$ cannot be used in an $X$-saturated matching, because it would use one of the vertices of $N(A)$ and none of $A$, that is, some vertex of $A$ would be left without a pair.
As for $(b)$, use the advice of @DarijGrinberg.
I hope this helps $\ddot\smile$
