Let M be a matching in a graph G, and let C be a cover of G. Every vertex in C is saturated by M. Prove that any augmenting path of M must have two consecutive vertices in C.
Not sure how to go about proving this. I played around with a few graphs and see that it works, but dont know how to do this proof.
By the definition of an augmenting path, we know that it must start and end on vertices which are not in C. (that are distinct) Also each edge must be alternating from being in M and not in M.
Could somebody help me out, thanks.
Not sure how to go about proving this. I played around with a few graphs and see that it works, but dont know how to do this proof.
By the definition of an augmenting path, we know that it must start and end on vertices which are not in C. (that are distinct) Also each edge must be alternating from being in M and not in M.
Could somebody help me out, thanks.