# Minimal coverings by maximal cliques

Let $G=(V,E)$ be an infinite simple, undirected graph. Let $\text{MC}(G)$ denote the set of maximal cliques in $G$. It is easy to see that the union of $\text{MC}(G)$ is $V$, so $\text{MC}(G)$ is a vertex cover of $G$.

If ${\cal C} \subseteq \text{MC}(G)$ is a vertex cover, is there a vertex cover ${\cal M}\subseteq {\cal C}$ that is minimal cover with respect to set inclusion? (A cover ${\cal M}$ is minimal if and only if for every $M\in {\cal M}$ we have that $\bigcup \big({\cal M}\setminus \{M\}\big) \neq V(G)$.)

Theorem. There is a graph $G$ such that there is no minimal vertex covering of it by maximal cliques. Indeed, in every vertex covering $\cal C$ of $G$ by maximal cliques, every vertex appears in infinitely many of the cliques in $\cal C$, and so one can omit any desired clique from $\cal C$ and still have a vertex covering.
Proof. Consider the tree of finite binary sequences $G=2^{<\omega}$, considered as a graph where every node has an edge with its initial segments and its extensions. So the cliques are precisely the linearly ordered sets, and the maximal cliques are precisely the branches through the binary tree.
In particular, the covering $\cal C$ is not minimal, and any given element of it can be omitted and still give a covering. QED