# Covering an infinite graph by cliques

If $G=(V,E)$ is any nonempty, simple, undirected graph (finite or infinite), it can be covered with cliques in many ways, the least interesting being a cover by singletons. However, there is one clique cover that I am not sure exists at all in infinite graphs. But first, let's get the "terms and conditions" right.

Let us call a collection ${\cal M}$ of non-empty subsets of $V$ a clique cover if $\bigcup {\cal M} = V$ and every member of ${\cal M}$ is a clique (when regarded as an induced subgraph of $G$). We call it special if for any clique cover ${\cal J}$ of $G$ we have $|{\cal M}\setminus {\cal J}| \le |{\cal J}\setminus {\cal M}|$.

Question. Does any nonempty graph have a special clique cover? (The answer is yes for finite graphs.)

• Small terminological comment: it would be shorter, and type-wise clearer, to replace "is a clique (when regarded as an induced subgraph of $G$)" with "induces a clique of $G$". – Peter Heinig Aug 1 '17 at 20:29
• By the way, a clique cover of $G$ is nothing more than a proper vertex colouring of its complement. So it can also be phased as a vertex colouring problem. – Jon Noel Aug 1 '17 at 21:16
• @JonNoel That's nice - do you know a solution of this vertex colouring problem? – Dominic van der Zypen Aug 2 '17 at 8:37