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\)."