# Graphs Problem 5

### Solution

We must show that R is reflexive, symmetric, and transitive.

#### Reflexive

Let $$u \in V$$. Then uRu because there is a length zero path from u to u containing no edges.

#### Symmetric

Let $$u,v \in V$$. Suppose uRv, so there is a path P from u to v. To get a path from v to u we simply reverse the path P. So if P consists of the following sequence of n edges, $$e_1,e_2,\ldots,e_n$$, then the sequence $$e_n, e_{n-1},\ldots e_1$$ represents a path from v to u.

#### Transitive

Let $$u,v,w \in V$$. The important thing to note here is that we cannot simply travel along the path from u to v and then along the path from v to w as these paths may share nodes. In this case, combining the two may create a walk as opposed to a path. Instead, travel along the path from u to v until you reach the first point of intersection with the path from v to w. Call this vertex x. After you have reached x, travel along the path from v to w until you reach w. This new walk will be a path since we never repeat any nodes.

Since R is reflexive, symmetric, and transitive, R is an equivalence relation.

### Self-check

When you proved each property (reflexive, symmetric, transitive), did you introduce the variable(s) for the node(s) used in that part of the proof? E.g. in the transitive part "Let $$u,v,w \in V$$."