Grafteori/ Kombinatorik

Min uppgift: Let M be a matching in a bipartite graph G. Show that if M is supoptimal, then G contains an augmenting path with respect to M. Does this fact generalize to matchings in non-bipartite graphs?

Min lösning hittills:

Så M är suboptimal, det innebär att färre kanter är inblandade än i någon annan matchning i G. Dvs det finns omatchade kanter som en "augemented path" kan ta. Men hur kommer jag vidare?