How many different ways can single directed edge be added.... (graph theory) Let G be the following directed graph:

In how many different ways can a single directed edge be added to G3 so that there is a cycle
of length 8 starting at vertex A?

I tried a few ways of inserting a directed edge, but all of them won't give me a cycle because it will go through one of the vertices at least twice or it will end up in a dead-end. Here are some of my attempts.

This graph ends in a dead-end


This graph will not be a cycle because it will pass vertex F two times. (And the length won't be 8 anyways)

In this attempt, I did find a way to insert a directed edge but I am not sure if this is legal.


Can anyone help me with this, I am new to graph theory and I am a little confused about how to proceed. Thank you in advance.
 A: You have successfully found the only edge that works, but we can do this more systematically.
We can describe the graph we have right now in three groups:

*

*A $4$-cycle with edges $A \to B, B \to F, F \to E, E \to A$;

*A $4$-cycle with edges $C \to D, D \to H, H \to G, G \to C$;

*The edge $F \to G$.

If we add a new edge and get a cycle through all $8$ vertices, that cycle cannot contain all four edges $A \to B, B \to F, F \to E, E \to A$: then it would come back to $A$ too early. Similarly, it cannot contain all four edges $C \to D, D \to H, H \to G, G \to C$.
But the cycle must have $8$ edges; the only way to get to $8$ is to use $3$ edges from group 1, $3$ edges from group 2, the edge $F \to G$, and the new edge we're going to add.
If the cycle is using edge $F \to G$, then it can't use $F \to E$ or $H \to G$. (The cycles should only leave $F$ once, and it should only enter $G$ once.) This means we know exactly which edges of the current graph it uses.
Those edges can be put together into a $7$-edge path: $$E \to A, A \to B, B \to F, F \to G, G \to C, C \to D, D\to H.$$
The only edge that can turn this $7$-edge path into a cycle is the edge $H \to E$, which is the edge you found.
(The condition that the cycle must start at $A$ is a red herring: once we have a cycle through all $8$ vertices, we can start it anywhere we like.)
