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, NashWilliams 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