$R\subset S\times S$ for $S=\{1,2,3\}$: A Graph-Theoretic Approach

100 Views Asked by At

So I am given the relation $R=\{(1,1),(2,2),(3,3),(1,2),(1,3)\}$ and asked which of the properties reflexive, symmetric, or transitive are held in the relation, but what I am thinking is that this can be represented as a graph like this:

enter image description here

Is there a theorem that states that all equivalence classes must be connected in some particular fashion?

1

There are 1 best solutions below

5
On BEST ANSWER

Your directed graph for $R$ is correct. From it you should be able quite easily to see that $R$ has exactly two of the three properties.

The answer to your actual question is yes. If $C$ is an equivalence class of an equivalence relation $R$, and $G$ is the directed graph of $R$, then $C$ together with its associated edges will be a connected component of $G$: every possible directed edge between vertices of $C$ will be present in $G$. Moreover, there will be no edges between different equivalence classes. Conversely, if a directed graph has that structure, it’s the digraph associated with an equivalence relation on its vertices, with two vertices being related precisely in case they are joined by an edge.