Let $G=(V,E)$ be an undirected, simple graph. Let $\text{Ind}(G)$ be the set of [independent][1] subsets of $V(G)$. We say that $K\subseteq \text{Ind}(G)$ is a *cover (by independent subsets)* if $\bigcup K = V(G)$ and denote the collection of all such covers with $\text{CovInd}(G)$.

We call a cover $M\in \text{CovInd}(G)$ *strongly minimal* if for all $K\in \text{CovInd}(G)$ we have $$|M\setminus K| \leq |K\setminus M|.$$ It is easy to show that strongly minimal covers are minimal elements of $\text{CovInd}(G)$ with respect to set inclusion. It's also easy to see that the cardinality of any strongly minimal cover equals $\text{min}\{|C|: C\in\text{CovInd}(G)\}$. (Both statements are valid for finite as well as infinite graphs.)

**Question.** Does every graph have a strongly minimal cover by independent subsets? (The answer is trivially positive for finite graphs.)


  [1]: http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29