Graphs Problem 5

Buggy Solution

Here is a partly-correct solution to the problem. It's on the right track but has a few bugs. See how it compares to your draft 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.

Transitive

Let \(u,v,w \in V\). Suppose uRv and vRw. Then there is a path P from u to v, and another path Q from v to w. We join P and Q together at their common endpoint making a path from u to w.

Thus R is an equivalence relation.

Comments

The reflexive part is fine.

The symmetric part has the right idea, but you could supply more specifics. Suppose the path from u to v has the edge sequence \(e_1,e_2,\ldots,e_n\). Then what is the edge sequence for the path from v to u? This kind of detail isn't always necessary, but this is a good place to practice producing it when required.

The transitive part has a significant technical problem. Remember that a path cannot repeat nodes. However, the path from u to v might pass through a node x that's also on the path from v to w. If this is true, then joining the two paths end-to-end will produce a walk that isn't a path. It takes a detour at x, goes through some other nodes, and comes back to x again before proceeding to w. If your draft solution has this problem, figure out how to modify your construction to avoid the unnecessary detour.

When you've addressed these issues, move on to look at the full solution