In the problem below, a graph is a pair G = (V, E), where V is a finite set and

Question

In the problem below, a graph is a pair G = (V, E), where V is a finite set and E V 2 is a set of 2-element subsets of V . (None of the questions is about multigraphs.) A path in a graph G = (V, E) is a sequence of distinct vertices p = (v1, v2, . . . , vk), for some k N, such that there is an edge between any two consecutive vertices in p.

In each case, either prove that R is an equivalence relation for every graph G = (V, E) or find a graph G = (V, E) for which R is not an equivalence relation. (a) Let R be the relation on V consisting pairs of vertices (a, b) V × V such that a = b or there is a path (a = v1, v2, . . . , vk = b) for some odd integer k. (b) Let R be the relation on V consisting pairs of vertices (a, b) V × V such that a = b or there is a path (a = v1, v2, . . . , vk = b) for some even integer k.

Explanation / Answer

a) It is not an equivalence relation. As it is not transitive.
Reflexive (a,a): Yes as (a,a) belongs to R as per definiton
Symmetric (a,b) => (b,a): If there is a path from a to b of length k(odd), then there will always be a path from b to a of length k(odd)(reversing the a to b path).
Transitive (a,b),(b,c) => (a,c): Let's assume we have a path from a to b of some odd length k1, and a path from b to c of odd length k2, then there is no surity that there will be a path from a to c of some odd length. What we get from (a,b) and (b,c) belonging to R is that there is a path from a to c of length k1+k2(concatenating a to b and b to c paths), but k1+k2 is even(odd+odd=even), hence (a,b) and (b,c) do not imply (a,c)

b) It is an equivalence relation..
Reflexive (a,a): Yes as (a,a) belongs to R as per definiton
Symmetric (a,b) => (b,a): If there is a path from a to b of length k(even), then there will always be a path from b to a of length k(reversing the a to b path).
Transitive (a,b),(b,c) => (a,c): Let's assume we have a path from a to b of some even length k1, and a path from b to c of even length k2, then there is surity that there will be a path from a to c of some even length. What we get from (a,b) and (b,c) belonging to R is that there is a path from a to c of length k1+k2(concatenating a to b and b to c paths), and k1+k2 is even(even+even=even), hence (a,b) and (b,c) imply (a,c)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.