I came across an abstract algebra exercise, here it is:
Let $R$ be a reflexive and symmetric relation defined on set $E$. Consider on $E$ the relation $S$ defined by:
$x\, S\, y$ (equivalent) (there exist) $n\in \Bbb N^*$ and there exists a sequence ($x_p)_{0\leq p\leq n}$ of elements of $E$ such that
$x = x_0$, $y = x_n$ and $x_p\,R\, x_{p+1}$ if $0\leq p\leq n-1$.
Q: show that $S$ is an equivalence relation.
proving reflexive is easy aka. $x\, S\, x$ however symmetric and transitive are a bit tricky
Ok, so we will try to solve the symmetric and transitive aspect of the equivalence relation.
$\textbf{Symmetric:}\ \ xSy \Leftrightarrow ySx$
$xSy \Rightarrow$ we have a sequence as stated in the definition of the relation. Then we can form a new sequence $\{y_p\}_{0\le p \le n}$ by reversing the numbers starting from $y_0 = y$ and $y_n =x$ and $y_p = x_{n-p}\ \forall \ 0< p < n.$ Then we can see that $y_p R y_{p+1}\ \forall\ 0 \le p \le n-1$ as they are elements of $\{x_p\}_{0\le p\le n}$ and they are related via $R$ which is itself symmetric and transitive (Here we used symmetric nature of $R$).
Therefore $ySx$. Similarly, we can show $xSy$.
$\textbf{Transitive:}\ \ xSy, ySz \Rightarrow xSz$
Again by definition of relation, we have two sequences one for $xSy$ and other for $ySz$. Say they are $\{x_p\}_{0\le p \le n_1}$ and $\{y_k\}_{0 \le k \le n_2}$ respectively for some non-zero $n_1,n_2$.
Note the last term of the first sequence and the first term of the second sequence are same i.e. $y$ so we can form a new sequence by concatenation of the above two sequences i.e. our new sequence is $x_0 = x,x_1,x_2,...,x_{n_1}=y = y_0, y_1,y_2,...,y_{n_2}=z$. This new sequence has length $n_1+n_2$ and satisfies all properties of our relation $S$. Hence $xSz$. Therefore the relation $S$ is transitive.
Hence $S$ is an equivalence relation.
Note: The relation $R$ is not assumed to be transitive because the above argument for proving $S$ transitive doesn't require transitivity of $R$. Only symmetric nature of $R$ is sufficient.