<< No, because you need the graph to be k-regular, not merely have minimum degree k. >> Why is this? Hall's theorem makes no mention of regularity (in any sense). WFL On 5/31/15, Adam P. Goucher <apgoucher@gmx.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun