I am quite stuck with the following problem:
Let $M$ be a set and $S \subseteq M^2$. Define the relation $\sim$ as
$ a \sim b :\Leftrightarrow \exists x_0, x_1, ..., x_{n-1} \in M$ with $x_0 = a$ and $x_n = b$ s.t. $\forall i \in \{1, ..., n\}$ it is $(x_{i-1}, x_i) \in S$ or $(x_i, x_{i-1}) \in S$. Under what conditions is this relation an equivalence relation?
Of course, I know the criteria for equivalence relations, i.e. reflexivity, symmetry and transitivity. I also tried to sketch the problem, interpreting the $x_i$ as nodes and the $(x_i, x_{i-1})$ as edges but I am not too familiar with graph theory. In short, I don't seem to grasp what has to be considered here.
You have symmetry ($\forall (a,b) \in M^2, a \sim b \implies b \sim a$ by taking the reverse sequence) and reflexivity ($\forall a \in M, a \sim a$ by taking the sequence $(a)$).
Let $(a, b, c) \in M^3$ such that $a \sim b$ and $b \sim c$. You need to have transitivity (ie to always have $a \sim c$).
Let $x_0, ..., x_n$ be a sequence leading from $a$ to $b$ and $x_n, ..., x_{n'}$ from $b$ to $c$. You then have $x_0, ..., x_n, ..., x_{n'}$ which is a sequence that leads from $a$ to $c$ therefore $a\sim c$
Thus your relation is always an equivalence relation