I have noticed that in the blossom algorithm, we need to find the blossom while finding the augmenting path. What will happen if I just know there is a blossom in a graph and the contracted graph has an augmenting path. Will the original graph not have that augmenting path or will be same?
Edit to make it clear:- This is problem 8 from Chapter 10 from Combinatorial Optimization: Algorithms and Complexity Christos H. Papadimitriou
Theorem : Suppose that, while searching for an augmenting path, from a node u of a graph G with respect to a matching M, we discover a blossom b. Then there is an augmenting path from u in G with respect to M iff there is one from u (vb if u is the basis of b) in G/b with respect to M/b.
Show by an example that if G = (V;E) is a graph, M a matching of G, and b a blossom (a circuit with 2m + 1 edges, m of which are in M), then the following may fail to be true : There is an augmenting path in G with respect to M iff there is one in G/b with respect to M/b. Compare with above theorem.
What does "just know" mean? It is hardly something that would be part of an algorithm.
But the important thing to note is that each iteration of the algorithm starts with a valid (possibly null) solution and finds either a better solution or a simpler form of the graph.
So if at any time, you have some magic way of producing a better solution, independent of the algorithm, there's no reason you couldn't simply use it, and then continue using the algorithm on that improved intermediate solution.