# A proof: a bipartite graph with 2n vertices whose largest independent set size is n has a perfect matching

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.

Barak.

• What does (**) refer to? Jul 18 '18 at 21:56
• Hey Mike, edited, thanks. Jul 19 '18 at 4:22

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.
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.