0
$\begingroup$

How Symmetric difference of augmenting path with matching increases matching length by 1?

I know that augmenting path means unmatched start and end edges and alternating matched and unmatched edges. Even edges in symmetric difference are matched edges in matching and odd edges from augmenting path. It will increase but how by 1 unit? I could sense this with example but not able to think about proof. Please explain....

PS - i just started graph theory by douglas west. Pls bear with my ignorance

$\endgroup$
0
$\begingroup$

enter image description here

Your intuition is correct. We will need to increase the path length by 2. Later in the book the author will probably describe a process where IF we have a partial matching & we can find an alternating path between two points that are not included in the matching THEN we can replace the matching by a new one by alternating the edges of this path. THIS will cause the size of our matching to increase by $1$.

$\endgroup$
  • $\begingroup$ sir it will increase for sure. But how by 1 unit? this part i did not understood. I could sense this with an example. But how to prove? $\endgroup$ – Nascimento de Cos May 13 '19 at 23:57

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.