Bipartite Graphs & Matching

A bipartite graph $G=(V,E)$ is a graph whose vertex set $V$ can be divided into two disjoint sets $L$ and $R$, such that every edge connects a vertex in $L$ to one in $R$, with no edges within the same set.

A matching in a bipartite graph is subgraph $M=(V^{\prime }\subseteq V,E^{\prime }\subseteq E)$ whereby no two edges share a common vertex. The cardinality of any matching is $|M|=\frac{|V^{\prime }|}{2}$.

A maximum-cardinality matching is a matching that results in the largest cardinality (i.e. set size) of the matched edges $E^{\prime }$.

A perfect matching is a matching that covers every vertex of $G$. That is, $V^{\prime }=V$ and $|E^{\prime }|=\frac{|V|}{2}$ (each edge connects two vertices).