I'm told that the problem lies behind the possible odd cylces in general graphs. However, I can't find any counterexamples and get confused.
For example, one says that if we do DFS in the graph below starting from 6 in the order of 4-5-1-2-3, we'll miss the augmenting path. But I think starting a search from every unsaturated vertex would solve the problem, since a DFS from 1 in the order of 6-5-1-2-3-4 results in an augmenting path.
For another example, one says that if we do DFS in an odd cycle, we'll get stuck in an infinite loop. But should we visit the vertex that has been visited before? I think that's unnecessary.
I would be extremely appreciative of any assistance!
Best Answer
It's possible for the same issue to arise starting from every vertex.
Consider the following diagram:
Here, $1$ and $10$ are the two vertices unsaturated by the matching $\{23, 45, 67, 89\}$, and $(1,2,3,4,5,6,7,8,9,10)$ is an augmenting path. But we won't find it starting from vertex $1$ if we happen to explore from $1$ to $5$ first: we'll walk $(1,5,4,3,2)$ and get stuck. Similarly, we won't find it starting from vertex $10$ if we happen to explore from $10$ to $6$ first: we'll walk $(10,6,7,8,9)$ and get stuck.