## Introduction

Let \(G=(V, E)\) be an undirected graph. Matching in \(G\) is a subset of edges \(M \subseteq E\) such that at most one edge is incident to each vertex in \(V\).

A vertex is *matched* is it is incident to some edge in \(M\), otherwise it is called *free* or *exposed*.

## Augmenting Paths

- Alternating path: a path in which the edges belong alternatively to the matching and not to the matching
- Augmenting path: an alternating path that starts from and ends on exposed vertices

Clearly, an augmenting path can be ‘flipped’ to increase the matching size **by one**, i.e., just make free vertex matched and make matched vertex free in this path.

**Berge’s Theorem**: The matching M is maximum **iff** there is no augmenting path w.r.t. \(M\). I personally think the proof is easy but quite powerful.

Thus, we can immediately use the theorem to design an algorithm: find augmenting path iteratively until no more can be found. The problem is how we can find the augmenting path.

## Algorithm for bipartite graph

FIND-AUGMENTING-PATH(\(G=(V_1 \cup V_2, E), M\))

- \(V'_1\) = a set of free vertices in \(V_1\)
- \(V'_2\) = a set of free vertices in \(V_2\)
- Construct the directed graph \(G_M = (V_1 \cup V_2, E_M)\)
- \(E_M\) is a set of directed edges such that it includes all arcs from \(V_1\) to \(V_2\), and all matching arcs from \(V_2\) to \(V_1\)
- i.e., \(E_M = \{(v_1, v_2) : v_1, v_2 \in E \setminus M, v_1 \in V_1, v_2 \in V_2\} \cup \{(v_2, v_1) : v_1, v_2 \in M, v_1 \in V_1, v_2 \in V_2\}\)

- Find a simple path \(p\) from \(V'\_1\) to \(V'\_2\) in \(G_M\)

Note that the above graph \(G\_M\) is similar to the residual network in network flow. Apparently, \(p\) starts from a free vertex in \(V'\_1\) and ends at another free vertex in \(V'\_2\), thus it is an augmenting path.

## Complexity

The maximum size of matching is upper bounded by \(|V|/2\), and each step, the matching size is incremented by one. Thus, the number of augmenting path found will be at most \(O(|V|)\). At each step, it takes \(O(|E|)\) to find a path. Thus the overall running time is \(O(|V||E|)\).