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, 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? Just because the hypothesis is satisfied for an infinite graph G, that doesn't mean the hypothesis is satisfied for a finite subgraph A of G. There may be edges from vertices in A to vertices not in A, and when you ignore those vertices, then A won't have enough edges to have a matching; it may have no edges at all! This sort of argument works to show, for example, that if any finite subgraph of a graph is colorable with N colors, then so is the entire graph. But I don't think it works here. Hall's theorem is in fact true for infinite graphs, but the proof is more difficult than this. Andy