Let $X$ be a non-empty set. Consider $\mathcal{P}(X)$, the power-set of $X$. We say that $a,b \in \mathcal{P}(X)$ form an edge if and only if their symmetric difference is a singleton, i.e. $\textrm{card}((a\setminus b) \cup (b\setminus a)) = 1$.


It is clear that for a finite set $X$ the resulting graph has chromatic number 2: color those subsets of $X$ with an even number of members with color 1, and the rest with color 2.


For $X$ infinite, does the resulting graph still have chromatic number 2?



Chromatic number of the power set
Yes, for $X$ infinite the resulting graph also has chromatic number 2. To see this, just use the fact that a graph is bipartite if and only if it does not contain an odd cycle (this remains true for infinite graphs). An odd cycle in your graph quickly leads to a contradiction due to parity reasons. 


