A path constructed by repeatedly finding a path of positive capacity from a source to a sink and then adding it to the flow. An augmenting path for a matching M is a path with an odd number of edges e_1, e_2, ..., e_m such that e_odd not element M and e_even element M. The symmetric difference of M with {e_i}yields a matching having one more edge than M. Augmenting paths are used in the blossom algorithm and Hungarian maximum matching algorithm for finding graph maximum matchings.

Berge's theorem | blossom algorithm | hungarian maximum matching algorithm