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)$.)



Minimal coverings by maximal cliques
Nice question. The answer is no, not necessarily.


**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.


A covering set of maximal cliques is a set of branches that covers
the tree. But I claim that no covering set of branches is minimal,
since every node must be on infinitely many branches of the
covering, since that node lies below arbitrarily large families of incomparable nodes (even an infinite family), each of which lies on a different branch. So in any covering of the nodes of the tree with branches, any given branch is redundant.


In particular, the covering $\cal C$ is not minimal, and any given
element of it can be omitted and still give a covering. **QED**


