1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What does (**) refer to? $\endgroup$ Jul 18 '18 at 21:56
  • $\begingroup$ Hey Mike, edited, thanks. $\endgroup$
    – Barak B
    Jul 19 '18 at 4:22
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, that's a nice solution actually. Though what bothered me more than the complexity of my solution, is that my teacher claimed my solution is wrong, but I couldn't find a flaw in it, and it worried me. So I'm glad you agree this is correct. $\endgroup$
    – Barak B
    Jul 19 '18 at 4:38

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.