Maximum matchings in infinite graphs

Question

For any graph $G=(V,E)$ we define $\mu(G) = \sup\{|M|: M\subseteq E(G) \text{ is a matching}\}$.

Is there a graph $G=(V,E)$ such that for every matching $M\subseteq E$ we have $|M|<\mu(G)$?

Answer 1

Yes. First start off with the disjoint union $G=\bigcup_{n\in\mathbb{N}}K_n$ where $K_n$ is the complete graph on $\{1,\ldots,n\}$ for $n\in\mathbb{N}, n\geq 1$.

Note that this graph contains cliques of size $n$ for every $n\in\mathbb{N}$, but it does not contain a clique of size $\omega$.

Let $G^c$ be the complement of the graph $G$ constructed above. If we define its independence number to be $\alpha(G^c) = \sup\{|I|: I\subseteq V(G^c) \text{ and } I \text { is independent}\}$.

Clearly, every independent set of $G^c$ is finite, but $\alpha(G^c)=\omega$.

Finally we consider the line graph $L(G^c)$. Note that we have a correspondence of independent sets in $G^c$ and matchings in $L(G^c)$. Therefore $L(G^c)$ contains only finite matchings, but $\mu(L(G^c)) = \alpha(G^c) = \omega$.

Answer 2

No, this is not possible. Here is an elaboration of Eric Wofsey's comment.

Suppose it is possible and let $M$ be a maximal (under inclusion) matching of $G$ (this exists by Zorn's lemma). Then $|M| < \mu(G)$ by assumption. Let $X$ be the set of vertices not covered by $M$. Since $M$ is maximal, we have that $X$ is an independent set of vertices in $G$. Thus, for every matching $M'$ of $G$ and every $e \in M'$, $e$ has at most one endpoint in $X$. Thus, $|M'| \leq 2|M|$. If $M$ is finite, then $\mu(G)$ must be achieved by some finite matching since $\mu(G) \leq 2|M|$. If $|M|$ is infinite, $2|M|=|M'|$, so we are also done.