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.
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:
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.)