Construct a bipartite graph satisfying a condition The question is the following: for each $k \geq 2$, construct a $k$-regular bigraph with two edges such that they do not share a common vertex and they also never appear together in a perfect matching. To be honest, I have no idea how to solve this question. Any help is much appreciated.

Your goal is to force Hall's condition to be violated for the graph that remains once those two edges are chosen. Thing is, being $k$-regular (and nearly $k$-regular after two edges are chosen) means that the minimum size of a set violating Hall's condition is going to be pretty big: something like $k-1$ or $k-2$.

One way to to it is to start with two complete bipartite graphs of size $k$

![two complete bipartite graphs of size 4](

and modify them just slightly to connect them:

![slightly modified bipartite graph](

The two new edges have the property that any matching must use neither or both of them, so that the remaining vertices in the left and right halves have the correct number of targets. If we do something that's not compatible with that, such as choosing the two edges highlighted in blue below,

![two edges that don't go together](

then we get a violation of Hall's condition (highlighted in red), and the matching cannot be completed.