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)$.

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

$\displaystyle \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$

John Fremlin 2010-02-17