I was trying to prove the statement in the title:
Prove : A bipartite graph with 2n vertices whose largest independent set size
is n has a perfect matching.
I think I managed to solve it but I'm unsure whether or not my solution is right:
Firstly, I proved (easy to verify) that if G = ($V1 \cup V2$, E) then |V1| = |V2| = n.
(*)Secondly, I proved that each vertex has at least 1 neighbour. (if there's a vertex $x$ with no neighbours in V1 then $x \cup V2$ is an independent group of size n+1)
Then, I proved the statement using induction (on the size of V1). The base is simple (n=1)
Assuming that the statement is correct for a graph with |V1| = $n$. Assume G is a graph whose |V1| = n+1. If for every $S \subseteq V1$, $|N(S)| >= |S|$ (where N(S) is the set of neighbours of S vertices), then by the Hall Theorem, the graph has a perfect matching.
Else, assume that there exists $S \subseteq V1$ such that $|N(S)| < |S|$. According to (*) we can deduce that there exists $r \in N(S)$ that has at least 2 neighbours in S, denote them x,y. (**) Note that one of them, WLOG x, has $deg(x) > 1$, because if not, then both $deg(x) = deg(y) = 1$ and then $V2 \setminus\{ r\} \cup \{ x,y\}$ is an independent group of size n+2.
So now I remove r,x from G. Denote the graph without r,x as $G'$. Note that thanks to (**), $G'$ doesn't have an independent group os size n+1. Thus, by the induction assumption, $G'$ has a perfect matching $M'$.
And now $M = M' \cup \{ x,r \} $ is a perfect matching in G.
I'm hoping you could tell me if this proof is indeed correct.
Thanks in advance,
Barak.
Best Answer
I think it's right, although you could simplify things a little.
Note that any bipartite graph $G=(U,V,E)$ will have an independent set at least as big as the larger of the two parts, $\max(|U|,|V|)$. Thus in the given cases $|U|=|V| =n$.
Then for eliminating the case of $S \subseteq U$ with $|N(S)| < |S|$, we can simply note that this would imply that the independent set $S\cup (V-N(S))$ has more than $n$ vertices, which is not allowed.
This would also allow you to frame the proof without induction, since we can say:
For any subset $S\subseteq U$, $S\cup (V-N(S))$ forms an independent set. So we know that $n\ge |S\cup (V-N(S))|=|S|+|V|-|N(S)| $ giving $|N(S)|\geq|S|$ and thus Hall's marriage theorem applies.