## 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.