A matching M in G is a maximum matching if and only if G contains no augmenting path

 M-alternating path

Let M be a matching in G. An M alternating path in G is a path whose edges are alternately in E/M and M

M-augmenting path

M-augmenting path is an M-alternating path whose origin and terminus are M-unsaturated.

If G contains an augmented path P, then a matching M' can be found such that \[\left | M' \right |=\left | M \right |+1\]

A matching M in G is a maximum matching if and only if G contains no augmenting path

Let M be a matching in G, and suppose that G contains an M augmenting path \[v_0v_1v_2v_3...v_{2m+1}\]

Define \[M'\subseteq E\]by\[M'=(M\setminus (v_1v_2,v_3v_4,...,v_{2m+1}v_{2m}))\cup (v_0v-1,v_2v_3,...,v_{2m}v_{2m+1})\]Then M' is a matching in G, and\[\left | M' \right |=\left | M \right |+1\]

Thus M is not a maximum matching.

Implies M is a maximum matching then G contains no augmenting path.

Conversely,

 suppose that M is not a maximal matching and let M' be a maximum matching in G.

Set\[F=M'\bigtriangleup M\]where\[M'\bigtriangleup M\]denotes the symmetric difference of M and M'

(If G and H are graphs with vertex set V, then the symmetric difference \[G\bigtriangleup H\]is the graph with vertex set V whose edges are those edges appearing in exactly one of G and H

\[M'\bigtriangleup M=(M-M')\cup (M'-M)\])

Since M and M' are matchings, every vertex has atmost one incident edges from each of them. thus F has atmost two edges at each edge

Since\[\bigtriangleup (F)\leqslant 2\]every component is path or cycle

So here F consist of paths and cycles. The cycle have the same number of edges from M and M'. Since\[\left | M' \right |>\left | M \right |\], F must have a component with more edges of M' than M. Such a component can only be a path that starts and ends with edge of M'. that is M augmenting path in G.