Is there an example of an infinite connected, simple, undirected graph $G = (V,E)$ such that every vertex has $|V|$ neighbors, but $G$ does not have a perfect matching (that is, a set $M\subseteq E$ of pairwise disjoint edges such that $\bigcup M = V$)?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ What’s a perfect matching? $\endgroup$– Monroe EskewApr 23, 2018 at 7:49
-
$\begingroup$ A set $M$ of pairwise disjoint edges such that $\bigcup M = V$ $\endgroup$– Dominic van der ZypenApr 23, 2018 at 8:01
-
$\begingroup$ @BenBarber oh indeed, and it is answered by our student, and I remember now that I have seen this post :) $\endgroup$– Fedor PetrovApr 23, 2018 at 14:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Consider the ordering on $V$ such that for any vertex $v$ there exist less than $|V|$ vertices $y<x$. Construct the matching inductively.