91Ó°ÊÓ

Let \(M\) be a matching in a bipartite graph \(G .\) Show that if \(M\) is suboptimal, i.e. contains fewer edges than some other matching in \(G\), then \(G\) contains an augmenting path with respect to \(M\). Does this fact generalize to matchings in non-bipartite graphs?

Find a cubic graph without a 1-factor.

Prove the undirected version of the theorem of Gallai \& Milgram (without using the directed version).