I was learning about maximum matching in bipartite graphs but I can't understand one thing i.e. augmenting path always has one extra matching edge.
Link: Hopcroft Karp Algorithm Geeks for Geeks
Can someone please help me with this
Thank you in advance.
Augmenting path has an odd number of edges, let us name them $$$e_0, e_1, e_2, \ldots, e_{2 k}$$$.
The edges selected previously are $$$e_1, e_3, e_5, \ldots, e_{2 k - 1}$$$, there are $$$k$$$ of them.
If we instead select $$$e_0, e_2, e_4, \ldots, e_{2 k}$$$, there are $$$k + 1$$$ of them.
Thank you very much :)