Construction of the digraph

(0) Let C be a directed n-cycle $\overrightarrow{c_1 \dots c_n c_1}$, and v and w two vertices outside of C with edges $\overrightarrow{v c_i}$ and those $\overrightarrow{c_i w}$. We call such a graph a double-wheel. Note that the edges $\overrightarrow{v c_i}$and $\overrightarrow{c_i w}$ are non-flippable without making directed 3-cycles, while the edges $\overrightarrow{c_i c_{i+1}}$ are flippable.

(1) Let B be a directed cycle of size 4. Let us add 2 double-wheels whose directed cycles C₁ and C₂, respectively, are size 4 as Figure 1. Then the resulting graph H⁽¹⁾ has all the edges non-flippable except the eight edges in the two directed cycles C₁ and C₂. Note that the graph H⁽¹⁾ has no directed 3-cycles.

  

Figure 1: The graph H⁽¹⁾.

(2) As same as step (1), we add a pair of double-wheels to each flippable cycle as Figure 2. The resulting graph H⁽²⁾ has all the edges non-flippable except 16 edges in 4 directed cycles. Let us call the center cycle B and 4 flippable cycles C₁, C₂, C₃ and C₄. The graph H⁽²⁾ still has no directed 3-cycles.

  

Figure 2: The graph H⁽²⁾.

(3) Let H⁽²⁾₁, H⁽²⁾₂, H⁽²⁾₃and H⁽²⁾₄ be 4 copies of H⁽²⁾of step (2). Let us denote the center cycle of H_i by B_i.

Now identify the flippable cycles C_j of 4 graphs H⁽²⁾_i, for each j. The resulting graph H⁽³⁾ has 4 flippable cycles C_j ( $1 \leq j \leq 4$) and 4 non-flippable cycles B_k ( $1 \leq k \leq 4$), where the cycles C_j, B_k are mutually disjoint. Other edges are all non-flippable. Observe that this identification does not make no directed 3-cycles.

(4) Let H⁽³⁾₁, H⁽³⁾₂, H⁽³⁾₃ and H⁽³⁾₄ be n ($\geq 4$) copies of H⁽³⁾ of step (3), and each graph H⁽³⁾_k have 4 flippable cycles C_i(H⁽³⁾_k) ( $1 \leq i \leq 4$) and non-flippable cycle B_i(H⁽³⁾_k) which are mutually disjoint.

Now identify the cycle C_i(H⁽³⁾_k) with B_i(H⁽³⁾_k+1) for each fixed pair (i, j, k), where the summation is taken in modulo n. The resulting graph G has no directed 3-cycles and no flippable edges.