A graph represented by the edges that do not follow from transitivity

Question

I am doing project with my group mates and we would like to introduce a notion. The notion is the following. We are working with a transitive directed graphs. Let $D$ be a transitive directed graph and we would like to define a graph which is the same graph but where only the arcs that do not follow from transitivity are displayed. What is the best way to formally define such notion?

Answer 1

I assume that a directed graph $G=(V,E)$ is transitive, if $E$ is a transitive binary relation, that is for any vertices $v$, $u$, and $w$ of $G$ if $(v,u)\in E$ and $(u,w)\in E$ then $(v,w)\in E$. Then we can reduce the set of edges of a finite graph $G$ to a set $E’$ such that the transitive closure of $E’$ is $E$, as follows. Each strongly connected component $C$ of $G$ is a clique, so we pick an arbitrary Hamiltonian cycle of $C$ and add its edges to $E’$. Next, let $V’$ be an arbitrary subset of $V$ such that $V’$ contains exactly one element of each strongly connected component of $G$. A subgraph $G’$ of $G$ induced by $V’$ is acyclic. Let’s call an edge $(v,w)$ of $G’$ basic, provided there is no vertex $u$ of $G’$ such that both $(v,u)$ and $(u,w)$ are edges of $G’$. It can be shown that for any edge $(v,w)$ of $G’$ there exists a sequence $v=u_1, u_2,\dots, u_{n-1}, u_n=w$ of vertices of $G’$ such that all edges $(u_i, u_{i+1})$ are basic. We add to $E’$ all basic edges of $G’$. The construction of the set $E’$ is finished and it provides that $E$ is the transitive closure of $E’$.