The original problem is stated in terms of the tolerance relation (reflexive and symmetric, but not necessarily transitive): Is every tolerance subset contained in a maximal tolerance subset?
For a set $X$ with a tolerance relation $r \subset X \times X$, a subset $U \subset X$ is said to be a tolerance subset if $(a, b) \in r$ for any $a, b \in U$. A tolerance subset is maximal if it is not contained in any other tolerance subset.
The answer to the corresponding question for the equivalence relation is yes, but things get harder if transitivity is removed.
I tried to prove it and found it sufficient to show the existence of one maximal tolerance subset, i.e. every (possibly infinite) undirected graph contains a maximal clique.
Thank you!
This follows from Zorn's lemma: any vertex is a clique, and if cliques are ordered by inclusion the union of cliques in any chain is an upper bound.
Without Zorn, it is not true. For any equivalence relation you can define a graph where two elements are connected iff they are not equivalent, and then a maximal clique is precisely a set of representatives for the equivalence classes, which needs the axiom of choice.