On Mon, Jun 1, 2015 at 7:49 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Sent: Monday, June 01, 2015 at 11:50 AM From: "Andy Latto" <andy.latto@pobox.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Pairings in bipartite graphs
On Mon, Jun 1, 2015 at 3:05 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
I was merely commenting that k-regularity of a graph G is a sufficient condition for a matching to exist.
Claim: If G is a (not necessarily finite) k-regular bipartite graph, and 1 <= k < infinity, then a matching exists.
Proof: For each edge e in the graph, let P_e denote the proposition `the edge e is involved in the matching'. Then for each vertex v in the graph,
(of course I meant each vertex v in the vertex class X)
let the incident edges be denoted e_1, ..., e_k. Then write down the axiom (e_1 or e_2 or ... or e_k) and the axioms ((not e_i) or (not e_j)) (for all 1 <= i < j <= k).
Then any finite subset of the axioms is consistent, due to the result for finite graphs.
Why is that?
Take the induced subgraph consisting of all vertices in A and all of the neighbours thereof, where A is the subset of X consisting of all endpoints of edges mentioned [in the finite subset of the axioms].
That induced subgraph is not k-regular, since it contains the neighbors, but not the neighbors of the neighbors. This induced subgraph won't have a perfect matching; it doesn't even have the same number of vertices in the two parts! You can make this work, but the theorem you want to use for finite graphs is not one that says there's a perfect matching, but the related one that says that if given any subset of the first part of the graph, the set of vertices in the second part adjacent to at least one of them is at least as big as the subset, then there is a matching from the first part to a subset of the second part. This gives you, by the compactness argument, a matching from the first half to some subset of the second half, but this matching might not be onto (something that comes for free in the finite case, but not the infinite case. To complete the proof, reverse it, so you have a different matching between all of the second part and a subset of the first part, and then use the Shroeder-Bernstein trick to piece these together to produce a complete matching. Andy
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com