Is there a simple, undirected graph $G= (V,E)$ with $\chi(G) \geq \aleph_0$, and if $M\subseteq E$ is a matching then $|M|<\chi(G)$?
1 Answer
$\begingroup$
$\endgroup$
No. Take a maximal matching $M$. Its complement is independent set, that allows to color our graph with $2|M|+1$ colors. This is either finite or $|M|$, thus $|M|\geqslant \chi(G)$.