Matchings

Definition 5..1 ($k$-factor)  

A $k$-factor of a graph $G$ is a $k$-regular spanning subgraph, that is, a subgraph $H$ with $\delta(H) = \Delta(H) = k$.

Definition 5..2 (Matching)  

Let $G$ be a bipartite graph with vertex classes $X$ and $Y$. A matching in $G$ is a set of $\vert X\vert$ independent edges.

If $\vert X\vert = \vert Y\vert$ then a matching is a 1-factor.

Theorem 5..3 (Hall's marriage theorem)  

Let $G$ be a bipartite graph with vertex classes $X$ and $Y$. Then $G$ has a matching iff $\vert\Gamma(S)\vert \ge \vert S\vert$ for every $S \subseteq X$.

Proof. [Using Menger's theorem]

Join a new vertex $a$ to all elements of $X$ and a new vertex $b$ to all elements of $Y$ to form $G'$.

Suppose $C$ is a set of vertices separating $a$ from $b$. Then $\Gamma(X \setminus C) \subseteq Y \cap C$. Now $\vert C\vert = \vert C \cap X\vert + \vert C \cap Y\vert$. So $\vert C\vert \ge \vert C \cap X\vert + \vert\Gamma(X \setminus C)\vert$. By Hall's condition $\vert\Gamma(X \setminus C)\vert \ge \vert X\setminus C\vert$. So $\vert C\vert \ge \vert C \cap X\vert + \vert X \setminus C\vert = \vert X\vert$. By the choice of $C$, $\kappa(a,b;G) \ge \vert X\vert$.

Using Menger's theorem there are $\vert X\vert$ independent paths, giving a matching in $G$.

$\qedsymbol$

Proof. [Direct]

By induction on $\vert X\vert$.

The case $\vert X\vert \le 1$ is trivial.

Suppose that for every $S \subset X$ with $S \ne \emptyset,X$ we have $\vert\Gamma(S)\vert > \vert S\vert$. Then take any $xy \in E(G)$. $G - x$ satisfies Hall's condition. By the induction hypothesis $G - \{ x,y \}$ has a matching, so $G$ has a matching.

Otherwise there exists a critical set $T \subset X$, $T \ne \emptyset, X$ with $\vert\Gamma(T)\vert = \vert T\vert$. Let $G_1 = G[T\bigcup \Gamma(T)]$ and $G_2 = G[(X \setminus T) \bigcup (Y \setminus \Gamma(T))]$.

$G_1$ clearly satisfies Hall's condition. Let $S \subseteq X\setminus T$. Now $\Gamma_{G_2} (S) = \Gamma_G (S \bigcup T) \setminus \Gamma_G (T)$.

$$\vert\Gamma_{G_2} (S)\vert \ge \vert\Gamma_G (S \bigcup T)\vert - \vert\Gamma_G (T)\vert$$

$$\ge \vert S \bigcup T\vert - \vert T\vert = \vert S\vert$$

So by induction hypothesis there is a matching on $G_1$ and $G_2$, giving a matching in $G$.

$\qedsymbol$

Corollary 5..4 (Defect form of Hall's theorem)  

Let $d \ge 0$ be an integer. If $\vert\Gamma(S)\vert \ge \vert S\vert - d$ for all $S \subseteq X$ then there is a matching of all but $d$ elements of $X$.

Proof. Add $d$ extra vertices to $Y$ connected to all vertices of $X$. Then by Hall's theorem there is a matching. Remove the additional vertices, to make a matching of all but $d$ elements of $X$.

$\qedsymbol$

Corollary 5..5 (Polygamous form)  

Let $d \ge 1$ be an integer. If $\vert\Gamma(S)\vert \ge d\vert S\vert$ for all $S \subseteq X$, then we can match each $x \in X$ to $d$ elemens of $Y$, the different $d$ element sets being disjoint.

Proof. Replace each $x \in X$ with $d$ nodes connected to $\Gamma(x)$. Hall's theorem gives a matching.

$\qedsymbol$