Matchings without Hall’s theorem

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 M in a bipartite graph on vertex classes X and Y, an augmenting path is a path P from x \in X \setminus V(M) to y \in Y \setminus V(M) such that ever other edge of P is an edge of M.  Replace P \cap M by P \setminus M produces a matching M' with |M'| = |M| + 1.

Theorem.  Let G be a spanning subgraph of K_{n,n}.  If (i) \delta(G) \geq n/2 or (ii) G is k-regular, then G has a perfect matching.

Proof. Let M = \{x_1y_1, \ldots, x_ty_t\} be a maximal matching in G with V(M) \subset V(G).

(i) Choose x \in X \setminus V(M), y \in Y \setminus V(M).  We have N(x) \subseteq V(M) \cap Y and N(y) \subseteq V(M) \cap X.  Since \delta(G) \geq n/2 there is an i such that x is adjacent to y_i and y is adjacent to x_i.  Then xy_ix_iy is an augmenting path.

(ii) Without loss of generality, G is connected.  Form the directed graph D on v_1, \ldots, v_t by taking the directed edge \vec{v_iv_j}  (i \neq j) whenever x_iy_j is an edge of G.  Add directed edges arbitrarily to D to obtain a k-regular digraph D', which might contain multiple edges; since G is connected we have to add at least one directed edge.  The edge set of D' decomposes into directed cycles.  Choose a cycle C containing at least one new edge of D', and let P be a maximal sub-path of C containing only edges of D.  Let v_i, v_j be the start- and endpoints of P respectively.  Then we can choose y \in N(x_i) \setminus V(M) and x \in N(y_j) \setminus V(M), whence yQx is an augmenting path, where Q is the result of “pulling back” P from D to G, replacing each visit to a v_s in D by use of the edge y_sx_s of G. \square

 

Leave a Reply

Your e-mail address will not be published.