# 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?

• The argument you give for $\Longrightarrow$ is wrong. – darij grinberg Mar 12 '16 at 18:39
• (a) $\Longleftarrow$: Fix an edge $e$. You want a matching of $G$ that contains $e$. Remove the two endpoints of $e$ from $G$, and find a matching of the remaining graph (using Hall's theorem). – darij grinberg Mar 12 '16 at 18:43
• (a) $\Longrightarrow$: This is not true, even with the "nonempty" condition I've added. Just imagine that $G$ is a single edge! Maybe you want $A$ to be not only nonempty, but also not equal to the whole $X$. That said, I'd rather not guess the correct statement. – darij grinberg Mar 12 '16 at 18:45
• (b) This is classical; see, e.g., math.uni-hamburg.de/home/diestel/books/directions/aharoni.pdf . – darij grinberg Mar 12 '16 at 18:45
• yeah I forgot to put the statement "A is nonempty and not equal to the whole X". If that's the case, Is my $\Leftarrow$ correct? – Golden Mar 12 '16 at 19:19

$(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$