Is there a mistake in this proof of Hall's theorem?

Question

I was going over a proof of Hall's theorem in my textbook (Diestel, 3rd edition), and there appears to be a mistake. Though, there's probably a higher chance that I'm mistaken about something. I would appreciate some input. Here's the theorem and proof presented.

I'm having trouble with the inequality part of the proof (indicated by the arrow).

Let's consider an edge $ab$. Then $G' = G - (a,b)$. Thus we've removed $a$ and $b$, and all their incident edges. Let us now pick a subset of $A - a$ and call it $S$. There are three kinds of $S$.

1. A set that did not contain vertex $a$, and in which none of the neighbors of $S$ contained $b$ (except a ofcourse). In this case, $|N_{G'}(S)| = |N_G(S)|$.
2. A set that did not contain vertex $a$, but the neighbor of one or more vertices of S contained $b$. In this case, $|N_{G'}(S)| \lt |N_G(S)|$.
3. A set that contained vertex $a$, and the neighbors of one or more vertices of S contained b.
4. A set thant contained vertex $a$, but none of the neighbors in $S$ contained $b$

2) Is the one I'm having trouble with at the moment. In this case, the inequality indicated in the proof doesn't hold since $|N_{G'}(S)|$ is less than $|N_G(S)|$.

Am I misunderstanding something here?

Answer 1

Be assured that the "Second proof" is correct. It is in fact the "Proof of the Book" for this theorem.

It is a fact that for any $S\subset A\setminus\{a\}$ the set $N_{G'}(S)$ of "acceptable partners" $y\in B\ $ is at most one person smaller than $N_G(S)$, insofar as only person $b\in B$ has been eliminated. (Note that you should not count some number of edges, but the number of persons acceptable to at least one $x\in S$.)

Since at the particular spot in the proof we have assumed $\bigl|N_G(S)\bigr|\geq|S|+1$ for all subsets $S\subsetneq A$ we may conclude that $$\bigl|N_{G'}(S)\bigr|\geq \bigl|N_G(S)\bigr|-1\geq(|S|+1)-1=|S|\ .$$

Answer 2

If $G$ contains perfect matching of $A$ (and so will $G'$ to $A'$), and $G$ is a complete bipartite graph, then induction on $|B|$ will induce also $|A|$ but not vice versa, so if we induce $|A|$ and $|B|$ independently in different occurences, they will fulfill :

$$G - \{a\} \rightarrow |N(A')|=|B|$$ $$G - \{b\} \rightarrow |N(B')|\leq|B'|\lt|B|$$ because $|N(A')|$ doesn't follow $|A'|$ (still $|B|$) but $|N(B')|$ follows $|B'|$.

If we intersect both occurences the conditions follow with change on $|N(A')|$: $$G - \{a,b\} = (G-\{a\}) \cap (G-\{b\}) \rightarrow |N(A')|\neq|B|=|B'| \rightarrow |N(B')|\leq|N(A')|.$$

Now we add more assumption : if $|A|=|B|$ ($G$ is $K_{n,n}$) then $|N(B')|=|B'|=|B|-1$, so $|N(A')| \geq |B|-1$.

$|B|$ is $|N(A)|$ so $|N(A')|\geq|N(A)|-1$.

Then, if $G$ is a complete bipartite graph, $|N(A')|=|N_{G'} (S)|$ and $|N(A)|=|N_G (S)|$, so $$|N(A')|\gt|N(A)-1 \rightarrow |N_{G'} (S)|\gt|N_G (S)|-1.$$

You may find $|N_{G'} (S)|$ less than $|N_{G} (S)|$ if you assume $S$ contained vertex $a$, that's why the proof said $S$ must not be $A$ itself or any subset of it that contained $a$ both in $|N_{G'} (S)|$ and $|N_{G} (S)|$.