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
.