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?
k >= 1 is a necessary and sufficient condition (proof: Hall's marriage).
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.
No, because you need the graph to be k-regular, not merely have minimum degree k. Sincerely, Adam P. Goucher