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$
$\endgroup$
5
asked Nov 30, 2017 at 10:56
-
$\begingroup$ try Aharoni, Nash-Williams and Shelah. $\endgroup$– Uri BaderCommented 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$– DirkCommented Nov 30, 2017 at 11:34
-
$\begingroup$ @DirkLiebhold for complete graph on $\mathbb{R}$, you may easily avoid AC:) $\endgroup$– Fedor PetrovCommented 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$– DirkCommented Nov 30, 2017 at 11:39
-
$\begingroup$ Doesn't well ordering of $V$ + transfinite induction do the job? $\endgroup$– Aleksei KulikovCommented Nov 30, 2017 at 11:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Nov 30, 2017 at 11:51
-
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$– DirkCommented 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$ Commented 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$ Commented Nov 30, 2017 at 13:29