# Bipartite Matching Algorithm

This is an algorithm which looks for augmenting paths, used to prove Konig’s Theorem.

#### Pseudocode

Given a bipartite graph $G$ with bipartition $(A,B)$, and a matching $M$ of $G$.

- Let $X_{0}$ be the set of all unsaturated vertices in $A$.
- Set $X←X_{0}$ and $Y←∅$.
- Find all neighbours of $X$ in $B$ not currently in $Y$.
- (a) If one such vertex is unsaturated, then we have found an augmenting path. Make a larger matching by swapping edges in the augmenting path. Then start over at step 1.
- (b) If all such vertices are saturated, then put all of them in $Y$. Add their matching neighbours to $X$. Go to step 3.
- (c) If no such vertices exist, then stop. The matching is maximum, and the minimum cover is $Y∪(A\X)$.