Maximum minimum degree possible in a matchless graph.

Question

Let $n\leq m$ be positive integers.

What is the maximum possible value of $d$ such that there exists a bipartite graph $X,Y$ with $|X|=n$, $|Y|=m$ and minimum degree $d$ that admits no $X$ saturating matching?

Answer 1

It is $d = \lfloor\frac{n-1}{2}\rfloor$.

When $d < \frac n2$, we have the following construction. Partition $X$ into $X_1$ and $X_2$ with $|X_i| = d+1$, and partition $Y$ into $Y_1$ and $Y_2$ with $|Y_1| = d$. Then add all edges between $X_i$ and $Y_i$ for $i=1,2$. This has no $X$-saturating matching because the $d+1$ vertices in $X_1$ all want to be matched to the same $d$ vertices in $Y_1$.

When $d \ge \frac n2$, this does not work. (Vertices in $Y_2$ will not have the right minimum degree.) Here, we can show that there's an $X$-saturating matching by verifying Hall's condition. Let $S \subseteq X, S \neq \varnothing$. Then:

• If $|S| \le \frac n2$, then $|N(S)| \ge d \ge |S|$, because just one vertex in $S$ already has $d$ neighbors.
• If $|S| > \frac n2$, then $N(S) = Y$, because $|X \setminus S| < \frac n2 \le d$, so each vertex of $Y$ needs a neighbor in $S$ in order to reach the minimum degree of $d$. $|N(S)| = |Y| \ge |X| \ge |S|$.