Let $G$ be a bipartite graph. Prove that $\alpha(G) = |V(G)|/2$ if and only if G has a perfect matching.

Question

Let $G$ be a bipartite graph. Prove that $\alpha(G) = |V(G)|/2$ if and only if $G$ has a perfect matching.

$\alpha(G)$ is the independence number of $G$, i.e., the size of the maximum independent set of $G$.

I can't figure it out how to start this proof. I can see that this is true by looking at the picture in https://i.stack.imgur.com/lV4b9.png, but I can't formulate the proof. If anyone could help me writing the complete formal proof, I would be very grateful.

Answer 1

$(\Longleftarrow)$: Let $G$ be a bipartite graph, so by König 1931, Egerváry 1931, we have that the size of a maximum matching $\alpha'(G)$ equals the size of a minimum vertex-cover $\beta(G)$, that is $$\alpha'(G)=\beta(G)$$Now, by Gallai 1958, we have $$\alpha(G)+\beta(G)=|V(G)|$$Therefore $$2\alpha(G)=|V(G)|\iff \alpha(G)=\frac{1}{2}|V(G)|$$

can you continue from here to the other implications?

Answer 2

Since I've already basically given away the solution in the comments, I'll make the extra step to complete the proof. Please try to make a reasonable attempt before checking out the full solution:

Let $G$ be a bipartite graph of order $n$. First, note that $G$ has a perfect matching $\iff \alpha'(G) = \frac{n}{2}$ (this is obvious by the definitions of perfect matching and $\alpha'(G)$). The König-Egeváry theorem gives that $\alpha'(G) = \beta(G)$ (since $G$ is bipartite), while a result of Gallai gives that $\alpha(G) + \beta(G)= n$ (neither of these are particularly difficult to prove, but I will not do so here). Combining the above, we obtain $$\alpha(G) = n - \beta(G) = n - \alpha'(G),$$ and hence $$\alpha(G) = \frac{n}{2} \iff \alpha'(G) = \frac{n}{2},$$ as was to be shown.