2
$\begingroup$

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?

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

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
3
  • 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, 2017 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$ Nov 30, 2017 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$ Nov 30, 2017 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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