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]. Sincerely, Adam P. Goucher