How many different ways can single directed edge be added…. (graph theory)

directed graphsgraph theoryhamiltonian-path

Let G be the following directed graph:

enter image description here

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.

enter image description here

This graph ends in a dead-end


enter image description here

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.
enter image description here


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.

Best Answer

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:

  1. A $4$-cycle with edges $A \to B, B \to F, F \to E, E \to A$;
  2. A $4$-cycle with edges $C \to D, D \to H, H \to G, G \to C$;
  3. 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.)

Related Question