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$.

  • $\begingroup$ thanks! Can you point out, how you conclude that the augmenting path must have an odd number of edges? $\endgroup$ – alg Feb 17 '16 at 23:13
  • $\begingroup$ If a sequence alternates between two types of things, then if it has even length, it will start and end with different types, while if it has odd length, it will start and end with the same type. If that's not yet obviously true to you, how about this: if the sequence is for instance ABABAB... if there are an even number of elements, we can pair them into adjacent AB's , hence the sequence ends with a pair AB, so it ends with a B though it started with A. If there are an odd number of elements, we will have an A left over. $\endgroup$ – Lothar Narins Feb 18 '16 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.