Odd Cycles Break Augmenting

An odd cycle lets the search reach one vertex by both a matched and an unmatched edge, so flipping along the discovered walk yields a vertex covered twice. Deleting one vertex per odd component first restores the bipartite argument, at $O(VE)$ in the standard implementation.

An odd cycle lets the search reach one vertex by both a matched and an unmatched edge, so flipping along the discovered walk yields a vertex covered twice. Edmonds' blossom algorithm contracts each such cycle and searches the contracted graph, at $O(VE^2)$ in the standard implementation.

An odd cycle destroys the notion of an alternating path entirely, so no flip along any walk is well defined. Modelling the problem as min cost flow restores it by orienting every edge and pushing one unit per vertex, at $O(VE^2)$ in the standard implementation.

An odd cycle lets the search reach one vertex by both a matched and an unmatched edge, so flipping along the discovered walk yields a vertex covered twice. Kuhn's algorithm handles it by restarting the search from the other endpoint, at $O(VE)$ on a general graph.