3-dimensional cube shortest path question

Question

Let Q be the graph consisting of vertices and edges of a 3-dimensional cube. Two relations are defined on the vertices of Q.

• R1={(v,w):the shortest path from v to w has an odd number of edges}.

• R2={(v,w):the shortest path from v to w has an even number of edges.

• Exactly one of R1 and R2 is an equivalence relation

• Both R1 and R2 are equivalence relations

• None of R1 and R2 is an equivalence relation

My thoughts:

There is no such points (v,m) at 3-dimensional cube that have both even and odd number edges shortest path, so i would choose "None of R1 and R2 is an equivalence relation" based on this fact. -- wrong thoughts.

correct thinking: Choose any element in R1, call it x. Is xRx? Choose any two elements in R1 call them x, y. If xRy is yRx? And choose any three elements in R1, call them x,y,z If xRy and yRz, is xRz? Do the same for R2.

Please help if you have any thoughts, thank you.

Answer 1

An equivalence relation $R$, written $a \sim b$, satisfies the following properties:

• Reflexive: $a \sim a$
• Symmetric, if $a \sim b$, then $b \sim a$
• Transitive: if $a \sim b$ and $b \sim c$, then $a \sim c$.

$R_1$ is not an equivalence relation because it is not transitive: if you have an odd-length path from $a$ to $b$ and an odd-length from $b$ to $c$, then the path from $a$ to $c$ can have an even length (as adding two odds will give an even), provided it goes through $b$. (As MJD points out correctly above, it also isn't reflexive: the path from $a$ to $a$ has length $0$ and is of even length.)

$R_2$ is an equivalence relation: we have $a \sim a$ for any $a \in V$, where $V$ is the vertex set, as the length $0$ is even. Symmetry is obvious. Transitivity is also satisfied, because two evens always add to an even. That's not satisfactory though: this answer is incomplete; see comments.

Answer 2

Clearly $R_1$ is not an equivalence relation because it isn't reflexive.

However, $R_2$ is an equivalence relation, and you should prove this, as follows: First, look up the definition of an equivalence relation, including the three properties that characterize an equivalence relation. Then, for eac of the three properties, show that $R_2$ has that property.