# Given a bipartite graph $G=(U\cup V, E)$ with matching $M$, $|U|=|V|$. Why consists an augementing path of $M$ $2k+1$edges?

Let $G=(V,E)$ be a bipartit graph (with finitely many vertices and edges) with bipartition $\{U,V\}$, such that $U$ und $V$ have the same cardinality. Let $M\subseteq E$ be a matching and $P$ an augmenting path for $M$. In a book, the author claimes that $P$ consists of $2k+1$ edges (he says nothing about what $k$ is). I have no idea why this should be true.

Could you explain me, why under the conditions above $P$ consists of $2k+1$ edges?

Edit1: The condition $|U|=|V|$ seems to be unnecessary.

Edit2: Meanwhile I think $k$ should be the number of edges which are not in $M$.

I really appreciate your help. Regards

An augmenting path consists of edges alternating between edges of $M$ and edges not in $M$. It starts and ends at an unsaturated vertex, so it starts and ends with edges not in $M$. Hence it must have an odd number of edges, i.e. a number of the form $2k + 1$.