Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G = (V,E)$ be a simple and an undirected graph. Define a relation $R$ on the vertices of $G$ as follows: for two nodes $u$ and $v$, $(u,v) \in R$ if and only if there is a path from $u$ to $v$ in $G$.

a. Determine if $R$ is reflexive, symmetric, anti-symmetric, transitive or total.

b. Why is $R$ an equivalence relation?

c. Suppose $G$ is the graph below. What are the equivalence classes of $R$?

sample graph

share|improve this question
What have you tried? –  dtldarek Dec 13 '12 at 16:55
I need some kind of Hint to understand and start the problem , –  Hooman Dec 13 '12 at 16:57
Do you know the definitions of the terms in question? –  dtldarek Dec 13 '12 at 17:00
Yes , I know, But I don't understand a question completely –  Hooman Dec 13 '12 at 17:05
Then start by applying the definition of "reflexive" to $R$, to see if $R$ satisfies the definition. –  Chris Eagle Dec 13 '12 at 17:07

1 Answer 1

up vote 3 down vote accepted

The problem you presented is a very basic one, therefore you will get only very basic and general hints.



  • Is $R$ reflexive?
  • Check definition on Wikipedia or even better Wolfram.
  • $R$ is reflexive if (by definition) $\forall v \in V.\ (v,v) \in R$.
  • $R$ is reflexive, because each vertex is connected with itself by a path of length 0 (zero).
  • proceed in similar way with symmetry, anti-symmetry, transitivity and totality.


  • Is $R$ an equivalence relation?
  • Check definition here or here.
  • Answer using point (a).


  • Calculate all the elements that are in relation with $a$.
  • Calculate all the elements that are in relation with $b$.
  • Calculate all the elements that are in relation with $e$.
  • Observe, analyze, argue, answer.

I hope it will help you.

P.S. Please understand, this problem is elementary and it would be best if you would solve it by yourself!

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.