I learnt this definition "An augmenting path with respect to M is an alternating path in which the first and last vertices are exposed" in my class. What is an augmenting path with respect to M meaning ? let's say edges (2,9) (3,5) in M. My first augmenting path
$P_1$ is 1-2-9-3-5-6,
and my second augmenting path
$P_2$ is 1-2-9-6.
Which augmenting path is respect to M ?
If $P_1$ is respect to M, can I say that if P is an augmenting path with respect to M,then all edges in M is in P? Thanks in advance.
Matchings can be thought of as ways to color the edges of a graph as either black or red, as pictured above with the following stipulation that two red edges may never be adjacent to one another.
If a vertex is incident to a red edge, we say it has been saturated (or matched).
When we talk about a matching, $M$, we refer to it as the set of edges from the graph which we decided to color red. We will say a matching is maximal if there is no additional edge which can be added to $M$.
A maximum matching for the graph on the other hand, is one which has the most number of edges possible of any matching on the graph. Through a standard course in graph theory, you learn (and often prove) that a matching is maximum if and only if it contains no augmenting paths.
An augmenting path (for a graph with respect to a particular matching) is a path of odd length for which the edges alternate between white and red in color such that the first edge is white, the last edge is white, and the beginning and ending vertices are both not incident to any red edge and are different vertices.
In the above pictures, the first two graphs have augmenting paths, but the third does not.
By identifying an augmenting path, one can take the edges of the path, and change black edges to red, and red edges to black. Doing so will create a new valid matching which has strictly more red matched edges than before.
Note, those augmenting paths were augmenting paths specifically with respect to the original matching. They are no longer augmenting paths with respect to the new matchings.
As for the question of whether or not you must use all edges in a matching within an augmenting path, the answer is no. All that matters is what was said above for the definition of an augmenting path. Using all matched edges in the path is neither necessary nor in some circumstances even possible.
As for your examples, as I mentioned previously in the comments, your path ends with a saturated vertex and thus is not an augmenting path in both cases. Also, without knowing what the full set of edges in the graph and the full set of edges in the matching are, it is unknown if a path is in fact an augmenting path.