Proving a bipartite graph does not have a perfect matching

Question

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?

Answer 1

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

Answer 2

You can extend your example for greater values of $k$ relatively easily. For instance, if $k=3$, you could have "most" elements of $X$ and $Y$ connected to the same three elements of the other partition, and make sure that you have enough of them that you can apply Hall's Theorem like you essentially did here for the case $k=1$.

Answer 3

Let $X,Y$ be two disjoint sets of vertices with cardinal $k+1$. Take $x_0 \in X$ and $y_0 \in Y$, and define $G = (X\sqcup Y,E)$ where the set of edges $V$ is defined as : $$V = \big\{ \{x,y\} : x\in X, y\in Y \text{and } (x\neq x_0 \text{ or } y\neq y_0) \big\}$$

That way, every vertex in $X$ has an edge with every vertex in $Y - \{y_0\}$ so $\delta_{\min}(G) = k$. And, if $N$ is a perfect matching for $G$, it contains $k+1$ edges, each of which has one endpoint in $X - \{x_0\}$, which is absurd.