Equivalence/(Partial order) relation or any other suitable known relations?

26 Views Asked by At

Let $G$ be an indirected graph, let $V(G)$ and $E(G)$ be the set of vertices and edges of $G$, respectively. Define a relation $R$ on $G$ as: for all $v\in V(G)$ and $e\in E(G)$, $vRe$ if and only if $e$ is incident on $v$ and vice versa. Further, considering that $(v, v)=v$ i.e., the self loop $(v, v)$ coincides with the point $v$. Now, i wish to show that $R$ is an equivalence relation or any other suitable known relation on $G$. My effort: (1) Let $v\in V(G)$, then we can say that $v$ is incident on $v$ i.e., $vRv$; but what when $e\in E(G)$ is choosen? (2) Let $v\in V(G)$ and $e\in E(G)$, then $vRe\implies eRv$ or, for any $u, v\in V(G)$, $uRv\implies vRu$; but i have no idea of symmetricity when $v\in V(G)$ and $e\in E(G)$ is choosen or $e\in E(G)$ and $f\in E(G)$ is choosen? Lastly, transitive law seems to be failed. Please someone suggest me what type of the relation $R$ would be on $G$?

1

There are 1 best solutions below

1
On

Well, its not an equivalence relation. Its an inhomogeneous relation on $V\times E$. For an equivalence relation, you need to start from a homogeneous relation, say a relation on $V\times V$.

A prominent equivalence relation on an undirected graph $G$ is defined on $V\times V$, with $uRv$ iff there exists a path in $G$ between $u$ and $v$. The equivalence classes are then the connected components of $G$.