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?

  • $\begingroup$ try Aharoni, Nash-Williams and Shelah. $\endgroup$ – Uri Bader Nov 30 '17 at 11:07
  • $\begingroup$ 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. $\endgroup$ – Dirk Nov 30 '17 at 11:34
  • $\begingroup$ @DirkLiebhold for complete graph on $\mathbb{R}$, you may easily avoid AC:) $\endgroup$ – Fedor Petrov Nov 30 '17 at 11:35
  • 1
    $\begingroup$ @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. :) $\endgroup$ – Dirk Nov 30 '17 at 11:39
  • $\begingroup$ Doesn't well ordering of $V$ + transfinite induction do the job? $\endgroup$ – Aleksei Kulikov Nov 30 '17 at 11:39

Well, it seems like the following should work:

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.

  • 1
    $\begingroup$ 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...)? $\endgroup$ – Dirk Nov 30 '17 at 12:50
  • $\begingroup$ @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. $\endgroup$ – Aleksei Kulikov Nov 30 '17 at 13:20
  • $\begingroup$ 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$". $\endgroup$ – Aleksei Kulikov Nov 30 '17 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.