Given {{math|1=''G'' = (''V'', ''E'')}} and a matching ''{{mvar|M''}} of ''{{mvar|G''}}, a vertex ''{{mvar|v''}} is '''exposed''' if no edge of ''{{mvar|M''}} is incident with ''{{mvar|v''}}. A path in ''{{mvar|G''}} is an '''alternating path''', if its edges are alternately not in ''{{mvar|M''}} and in ''{{mvar|M''}} (or in ''{{mvar|M''}} and not in ''{{mvar|M''}}). An '''augmenting path''' ''{{mvar|P''}} is an alternating path that starts and ends at two distinct exposed vertices. Note that the number of unmatched edges in an augmenting path is greater by one than the number of matched edges, and hence the total number of edges in an augmenting path is odd. A '''matching augmentation''' along an augmenting path ''{{mvar|P''}} is the operation of replacing ''{{mvar|M''}} with a new matching :<math>M_1 = M \oplus P = ( M \setminus P ) \cup ( P \setminus M )</math>.
[[File:Edmonds augmenting path.svg|500px|alt=Augmentation along a path]]
By [[Berge's lemma]], matching ''{{mvar|M''}} is maximum if and only if there is no ''{{mvar|M''}}-augmenting path in ''{{mvar|G''}}.<ref name = "matching book">{{cite book
