Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
I need some kind of Hint to understand and start the problem , – Node.JS 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 – Node.JS 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
For example, $R$ would be reflexive if there is a path from each node to itself $(u,u) \in R$. (If you ask me, that would require the graph to have loops. Ie, the graph adjacency matrix should contain the diagonal. Often there's an implicit switch from the graph to its reflexive closure). – alancalvitti Dec 13 '12 at 17:11
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|cite|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.