I want to prove that for every $k \geq 1$, there exists a bipartite graph $G$ on sets $X$ and $Y$ such that $|X| = |Y|$, $\delta_{\min}(G) = k$ and $G$ has no perfect matchings.
For starters, I know that since $|X|=|Y|$, we have an even number of vertices, which is on the track to a perfect matching, so I can't use that as an argument.
I also know that the bipartite graph cannot be $k$-regular, since every $k$-regular bipartite graph has a perfect matching. But even being not $k$-regular isn't enough to prove that it doesn't have a perfect matching, since it is still possible to have one.
I've even come up with an example of a bipartite graph, in which $|X|=|Y|=3$, with minimum degree $\delta_{min}(G)=k=1$, in which the graph does not have a perfect matching (pictured above)
However, I am struggling to create a general proof for all $k\ge 1$, without simply providing a counterexample.
I could possibly use some level of Hall's Theorem, and say that for some subset $W$ of $X$, if $|W| > N|W|$, then we don't have a perfect matching. But then that negates any need for the problem specifying $|X|=|Y|$. Any thoughts on how to proceed?
Best Answer
Start out with the complete bipartite graph $K_{N,N}$ where $N$ is a very large number. now select a set $A$ of size $k+1$ in $X$ and a set $B$ of size $k$ in $Y$.
The graph that we want is the one we get when we remove all edges between $A$ and $Y\setminus B$. There can be no matching that satturates $A$ because they are only connected to vertices in $B$. On the other hand the vertices with the minimum degree are those in $A$, and they have degree $k$.