# Perfect matchings in infinite graphs

Let $G=(V,E)$ be an infinite graph such that $|V| = \kappa$ for some infinite cardinal $\kappa$, and every $v\in V$ has degree $\kappa$. Does $G$ have a perfect matching?

• try Aharoni, Nash-Williams and Shelah. – Uri Bader Nov 30 '17 at 11:07
• Do you allow Zorns lemma to show the existence of such a matching? If the graph gets complicated enough (e.g. complete graph on $\mathbb{R}$), you might not be able to get a matching any more concrete, even if it exists. – Dirk Nov 30 '17 at 11:34
• @DirkLiebhold for complete graph on $\mathbb{R}$, you may easily avoid AC:) – Fedor Petrov Nov 30 '17 at 11:35
• @FedorPetrov After thinking some more about it I agree that you can simply write a matching down. That poses the question if there are such graphs where you can't. :) – Dirk Nov 30 '17 at 11:39
• Doesn't well ordering of $V$ + transfinite induction do the job? – Aleksei Kulikov Nov 30 '17 at 11:39

Let us well order $V$ such that for every $v\in V$ set of $u$ such that $u < v$ has cardinality less then $|V|$. Now we are using transfinite induction to produce matching:
at each step if we are looking at vertex $v$ than if it is already in some pair with one of the previous vertices then just skip it and, otherwise, match it with smallest (under $<$) vertex which is connected with $v$ and not yet chosen. This vertex obviously exists(we already used less then $|V|$ vertices) and so we got our matching.
• You will get into trouble with the "at each step". This will only work if $V$ is countable, otherwise there is no way to look at elements of $V$ "step by step". Furthermore, how do you make sure that this is indeed a matching (so no vertex gets matched to more than one other vertex) and why can you assume that a well ordering of the above form exists such that the cardinality condition is fulfilled (I could give you a well ordering of the natural numbers, for example, where it is not fulfilled...)? – Dirk Nov 30 '17 at 12:50
• @DirkLiebhold Fact that such well ordering exists is well known: just take any well ordering and if any bad $v$ exists then let $v_0$ be smallest of them and then $\{ u \mid u < v_0 \}$ is well ordering we were seeking for. For what we constructed to be matching I added part " match it with smallest (under $<$) vertex which is connected with $v$ and not yet chosen." to assure that at any step there won't be any vertex connected with more than one other vertex. – Aleksei Kulikov Nov 30 '17 at 13:20
• And about "steps": there of course should be usual frase of the form: "Let us proof by induction that for any vertex $v_0$ there exists unique partial matching on $V$ such that it contains all vertices $u$ which are smaller of equal then $v_0$, every edge in that matching must contain at least one vertex which is not greater than $v_0$ and for each edge $(u, v)$ with $u < v$ then $v$ should be the smallest of vertices that are connected with $u$ and not in matching with any $w < u$". – Aleksei Kulikov Nov 30 '17 at 13:29