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 Cancel reply