In practice matchings are found not by following the proof of Hall’s theorem but by starting with some matching and improving it by finding augmenting paths. Given a matching in a bipartite graph on vertex classes and , an augmenting path is a path from to such that ever other edge of is an edge of . Replace by produces a matching with .
Theorem. Let be a spanning subgraph of . If (i) or (ii) is -regular, then has a perfect matching.
Proof. Let be a maximal matching in with .
(i) Choose , . We have and . Since there is an such that is adjacent to and is adjacent to . Then is an augmenting path.
(ii) Without loss of generality, is connected. Form the directed graph on by taking the directed edge () whenever is an edge of . Add directed edges arbitrarily to to obtain a -regular digraph , which might contain multiple edges; since is connected we have to add at least one directed edge. The edge set of decomposes into directed cycles. Choose a cycle containing at least one new edge of , and let be a maximal sub-path of containing only edges of . Let , be the start- and endpoints of respectively. Then we can choose and , whence is an augmenting path, where is the result of “pulling back” from to , replacing each visit to a in by use of the edge of .