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


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

  • 1
    $\begingroup$ I had thought of this example a few weeks ago, when trying to answer one of your previous questions on vertex coverings with cliques. $\endgroup$ – Joel David Hamkins Jan 2 '17 at 15:03
  • $\begingroup$ This infinite binary tree crossed my path a few times - but it didn't occur to me to consider it for this question. Thanks a lot (and happy new year)! $\endgroup$ – Dominic van der Zypen Jan 2 '17 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.