Let $G = (V,E)$ be an undirected graph and $M$ some matching of $G$. Let $T$ be a maximum matching of $G$ with $k := |T|$. I want to prove that if $|M| < k - \sqrt{k}$ then there exists a $M$-augmenting path of length at most $2\sqrt{k} - 1$.
I know that we have to consider the graph $G^{\prime} = (V, M \mathbin{\triangle} T)$ where $\triangle$ is the symmetric difference operator and there are at most $|T| - |M|$ vertex-disjoint $M$-augmenting paths but do not know how to proceed. Any help is appreciated.
Every vertex in $G'$ has degree at most $2$, with at most $1$ of that degree coming from each of $M$ and $T$. This limits the possible components in $G'$ to the following:
Even cycles, each with the same number of edges from $M$ and $T$.
Even paths, also with the same number of edges from $M$ and $T$.
Odd paths with one more edge from $T$ than from $M$; these are $M$-augmenting paths.
In general, there could be odd paths with one more edge from $M$ than from $T$; however, these would be $T$-augmenting paths, and by assumption $T$ is a maximum matching.
So in fact there are exactly $|T| - |M|$ vertex-disjoint $M$-augmenting paths to be found in $G'$: not at most $\sqrt k$ but at least $\sqrt k$.
Together with an upper bound on the number of edges in $G'$, this should be enough to show that one of those paths is shorter than $2\sqrt k- 1$.