Question

Suppose that ~ is a relation defined on the vertices of a graph G. There are three things we have to check to show that u ~ v is an equivalence relation: that it is reflexive, symmetric and transitive. Describe clearly what each one requires.

Answer 1

That's easy, just an process of equivalence relation.

Have a great day!!!

Solution:

We know that v~v since we have a path from a vertex to itself (the empty path). So i t is reflexive.

Let v,u∈V. If v~u Then there is a path from vv to uu. Inversely, if you walk that path from end to start, you get a path from uu to vv, so u~v. So it is symmetric.

Now let v,u,w∈V such that there is a path from v to u and from u to w. This trivially means that there is a path from v to w. Just go to u and from there go to w. So v~w which means transitivity.

So this is a required relation.