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

- every element of ${\cal C}$ is a clique, and
- $\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?