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

  • $\begingroup$ The argument you give for $\Longrightarrow$ is wrong. $\endgroup$ Mar 12 '16 at 18:39
  • $\begingroup$ (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). $\endgroup$ Mar 12 '16 at 18:43
  • $\begingroup$ (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. $\endgroup$ Mar 12 '16 at 18:45
  • $\begingroup$ (b) This is classical; see, e.g., math.uni-hamburg.de/home/diestel/books/directions/aharoni.pdf . $\endgroup$ Mar 12 '16 at 18:45
  • $\begingroup$ 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? $\endgroup$
    – 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.