Prove: The relation $v_i\mathcal{R}v_j\iff v_i\;\text{is adjacent to}\; v_j$ is not reflective or transitive or antisymmetric

67 Views Asked by At

Prove that the relation $\mathcal{R}$ defined on the set of vertices of a graph such that $$v_i\mathcal{R}v_j\iff v_i\;\text{is adjacent to}\; v_j$$ is not necessarily:

  1. Reflexive.
  2. Transitive.
  3. Antisymmetric.

Remember that a graph is a $3$-tuple $G=(V,A,\varphi)$ where $V\neq\emptyset$ is the set of vertices, $A$ is the set of edges and $\varphi\colon A\to V^{(2)}$ is the incidence function, where $V^{(2)}$ represents the set consisting of subsets of $1$ or $2$ elements of $V$.

Also, two vertices are adjacent if there exists a $a_k\in A$ such that $\varphi(a_k)=\{v_i,v_j\}$. That is, they are vertices that are joined by some edge.

With this, I tried the following:

  1. Let $G_1=(\{v_1,v_2\},\{a_1\},\varphi)$ where $\varphi(a_1)=\{v_1,v_2\}$:

    First graph

    We have $\mathcal{R}=\{(v_1,v_2)\}$ but it is not reflexive.

  2. Let $G_2=(\{v_1,v_2,v_3\},\{a_1,a_2\},\varphi)$ where $\varphi(a_1)=\{v_1,v_2\}$ and $\varphi(a_2)=\{v_1,v_3\}$:

    Second graph

    We have $\mathcal{R}=\{(v_1,v_2),(v_1,v_3)\}$ i.e. $v_2\mathcal{R}v_1$ and $v_1\mathcal{R}v_3$ but $v_2\!\not\!\!\mathcal{R}v_3$.

  3. Let $G_3=G_1$. We have that $v_1\mathcal{R}v_2$ and $v_2\mathcal{R}v_1$ but $v_1\neq v_2$.

Is my proof correct?

1

There are 1 best solutions below

8
On BEST ANSWER

In $(3)$ I would change the statement $$G_1=G_3$$ because they are not quite the same.

You may provide a different graph for part $3$ to inhance your solution.