Thm: Let $G=(V_1,V_2,E)$ be a bipartite graph s.t. (*) $|V_1|=|V_2|$, so:
There exists a perfect matching in G $\Leftrightarrow \forall S\subseteq V_1$,
$|N(S)|\ge|S|$
In this notation, $N(S)$ stands for the group of neighbours of all vertices in $S$.
Now, there's one part I'm stuck with at the proof, let me first show you guys what I've done so far:
"$\Leftarrow$":
(1) Let $S\subseteq V_1$ and assume: $|N(S)| \ge|S|$.
Let's proof by complete induction on $|V_1|$ that there's a perfect matching in $G$.(2) Induction assumption: Assume that for each $G=(V_1,V_2,E)$ satisfying (1), s.t. $|V_1|=|V_2|< n$, there's a perfect matching in $G$.
Induction step: Let $|V_1|=|V_2|=n$.
Case 1: $\forall S\subseteq V_1$, $|N(S)|>|S|$.
this case I proved already, so no reason to rewrite it.
Case 2: $\exists S\subsetneqq V_1$ s.t. $|N(S)|=|S|$, ($S\neq \emptyset$).Denote $G_1=(S,N(S),E_1), G_2=(V_1\backslash S,V_2\backslash N(S), E_2)$.
$E_1$ are the edges of $G$ between $S$ and $N(S)$, and $E_2$ are the edges of $G$ between $V_1\backslash S$ and $V_2\backslash N(S)$.I want to show that there's a perfect matching In $G_1$ and in $G_2$, therefore there's a perfect matching in $G$.
For $G_1$ I already proved, so we'll proceed with $G_2$:
$|V_1|=|V_2|$ and $|S|=|N(S)|$, so $|V_1\backslash S|=|V_2\backslash N(S)|$. This satisfies (*) (first line of the post).
since $\emptyset\neq S\subsetneqq V_1$, than $|V_1\backslash N(S)|<|V_1|=n$. This satisfies (2), and means we can almost use the induction assumption.
- We only need to find: $\forall T\subseteq V_1\backslash S$ holds that |$N_{G_2}(T)|\ge |T|$, where $N_{G_2}(T)$ stands for the group of neighbours of $T$ in $G_2$. That will satisfy (1) and will complete the proof.
So the last part of this quote is where I'm stuck, the other side of the proof is pretty easy and I already proved it.
Any help would be appreciated,
Thanks
Best Answer
Actually, all you need to show is that the inequality $N_{G_2}(U) \ge |U|$ holds for all $U \subseteq V_1 \setminus S$. Go back and reread your top paragraph which is shaded orange in your OP to see for yourself. We do this next.
Let $U \subseteq V_1 \setminus S$. Suppose that the strict inequality $|N_{G_2}(U)| < |U|$ holds.
Then on the one hand $N_G(U \cup S) \subseteq N(S) \cup N_{G_2}(U_2)$ [make sure you see why] and so $|N_G(U \cup S)|$ $\le |N(S)| + |N_{G_2}(U_2)|$ $=$ $|S| + |N_{G_2}(U_2)| < |S|+ |U|$.
On the other hand $U$ and $S$ are disjoint so $|U \cup S|=|U|+|S|$.
Can you finish from here.