Condition on a bipartite graph to have an $m$-factor - MathOverflow

Condition on a bipartite graph to have an $m$-factor

2011-05-17T08:36:19Z

This might be the most stupid question I am ever posting here: I am asking for a proof or a counterexample to a problem I proposed on MathLinks long ago.

Let $G$ be a bipartite graph, i. e., a graph such that the set of its vertices is the union of two sets $A$ and $B$, and each edge of the graph $G$ connects a vertex from $A$ with a vertex from $B$. For every subset $U$ of $A$ and every integer $k$, let $N_{k}\left(U\right)$ denote the set of all vertices from $B$ which have at least $k$ neighbours in the set $U$. Assume that $\left|A\right|=\left|B\right|$.

Some matchings of $G$ are called disjoint if there is no edge common to two or more of these matchings.

Let $m$ be a positive integer. Prove or disprove that the graph $G$ has $m$ disjoint perfect matchings if and only if the inequality $\left|N_{1}\left(U\right)\right|+\left|N_{2}\left(U\right)\right|+...+\left|N_{m}\left(U\right)\right|\geq m\left|U\right|$ holds for every subset $U$ of $A$.

Note that probably the assumption $\left|A\right|=\left|B\right|$ can be dropped if we replace "perfect matchings" by "$A$-complete matchings" (i. e., every vertex of $A$ is matched in every of these matchings). Also note that the "only if" direction is easy. Finally, of course, for $m=1$, this is Hall's marriage theorem.

The fact that I have posted the above problem on MathLinks in 2007 speaks for it being easy, but the fact that I have always been too lazy to write up my solution speaks for it being wrong. I have tried the obvious induction approach now, but I fail to obtain a reasonable inequality for $m-1$ instead of $m$ after deleting the first perfect matching. Any ideas?

Answer by Fedor Petrov for Condition on a bipartite graph to have an $m$-factor

2011-05-17T11:43:31Z

Take the general Ore-Ryser theorem:

Let $G$ be bipartite graph with vertex set $V=X\coprod Y$ ($X$, $Y$ parts) and $f:V\rightarrow {0,1,2,\dots}$ be a function such that $f\left(x\right)\leq\left(\text{degree of }x\right)$ for every $x\in X$. Then there exists a subgraph of $G$ (obtained from $G$ by removing some edges, not vertices), for which $f$ is degree function, if and only if for any $Y_1\subset Y$ one has $$ \sum_{y\in Y_1} f(y)\leq \sum_{x\in X} \min(f(x),d_{Y_1}(x)), $$ and this becomes an equality for $Y=Y_1$ (not necessarily only for $Y=Y_1$). Here, $d_{Y_1}(x)$ denotes the number of neighbors of $x$ in $Y_1$.

If $f(v)\equiv m$, it is easy to verify that we get your problem (or, strictly speaking, we get that one has a $m$-regular subgraph, but it is well known that it factors onto $m$ 1-regular subgraphs).

And the Ore-Ryser theorem may be proved by easy induction, the same as is used for the Hall marriage problem. Either there exists some nonempty $Y_1\ne Y$, for which the equality occurs, then we apply the induction propose for $X$ and $Y_1$ (with $f$ changed on $X$ to $\min(f,d_{Y_1})$) and then to $X$ and $Y\setminus Y_1$. Or we have strict inequalities for all nonempty $Y_1\ne Y$, then take any edge $xy$, remove it and replace $f(x)$ to $f(x)-1$, $f(y)$ to $f(y)-1$.

Answer by unknown (google) for Condition on a bipartite graph to have an $m$-factor

2011-11-14T15:45:57Z

Fedor, has this proof been published anywhere? I've been searching for an elementary proof (i.e. one not using Tutte's f-factor theorem) in print to reference. Also, do you happen to know why Ryser is given credit for the theorem? Many thanks.