[math-fun] Pairings in bipartite graphs

I thought of this problem when musing about Wilson's grid problem. Suppose we have a bipartite graph, with N vertices in each of two sets A and B. Further suppose that the graph is regular of degree k. For what values of N and k can we prove that there exists a bijection f between A and B such that a vertex and its partner are always connected by an edge of the original graph? The application to Wilson's problem is that there exists some radius r for which the points of one grid are always within r of at least k points of the other grid. This creates an infinite bipartite graph, and if such graphs always support pairings, that would establish r as an upper bound on the distance in Wilson's problem.