# Thread: Bipartite Graph

1. ## Bipartite Graph

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

Let alpha(G) = max size of an independent set of vertices
Let n(G) = the order of G

Any thoughts? Thanks!

2. Here is an outline of the proof. Try to fill up the details:

If G has a perfect matching, then its bipartition consists of two vertex sets A and B with equal cardinality. Choosing all the vertices of any one of these sets gives us the maximum independent set. If there exists a bigger independent set of at least n/2+1 vertices then we can use pigeonhole principle over it and the n/2 edges of the perfect matching to arrive at a contradiction.

Now let G contain a maximum independent set of size n/2. If there is such an independent set having vertices from both the A and B, then we can use induction. Otherwise, wlog consider the maximum independent set A. Now we can show that if for some subset A' of A defies Hall's condition, then A - A' will have a set of neighbours n(A-A') in B such that |n(A-A')| > |A-A'|, and obviously |n(A-A')| is disjoint from the neighbours of A'. From here we can obtain a bigger independent set.