Let G be a bipartite graph Prove that G VG2 if and only if

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

Solution

A perfect matching is a matching with |V |/2 edges. In a bipartite graph, a perfect matching can exist only if |L| = |R|, and we can think of it as defining a bijective mapping between L and R. For a subset A L, let us call N(A) R the neighborhood of A, that is, the set of vertices {r R : a A.(a, r) E} that are connected to vertices in A by an edge 4 in E. Clearly, if there is a perfect matching in a bipartite graph G = (V, E) with bipartition (L, R), then we must have |A| |N(A)|, because the edges of the perfect matching match each vertex in A to a distinct vertex in N(A), and this is impossible if |N(A)| < |A|.