Let $G=(V,E)$ be a simple, undirected graph. A *clique cover* is a set ${\cal C}\subseteq {\cal P}(V)$ such that 


1. every element of ${\cal C}$ is a clique, and
2. $\bigcup {\cal C} = V$.


We call a clique cover ${\cal C}$ *beatable* if there is a clique cover ${\cal C}\_1$ such that $$|{\cal C}\_1 - {\cal C}| < |{\cal C} - {\cal C}\_1|.$$
Non-beatable clique covers are called *unbeatable*.


It is easy to prove that every finite graph has an unbeatable clique cover. But what about infinite graphs?



Unbeatable clique covers
I think it is a known conjecture. The special case that there always exists a clique cover such that the union of any two of those cliques is not a clique, can be proved from Zorn's lemma (or without it), cf. my book with Totik: Problems and Theorems in Classical Set Theory, Problem 14.6.(m). This special case is actually equivalent to the axiom of choice: F. Galvin, P. Komjáth: Graph colorings and the axiom of choice, Periodica Math. Hung. 22 (1991), 71–75. 


