Graph theory - How many Hamiltonian Cycle in a non-complete graph

(In this representation of $\phi$, the first row specifies the edges and the second row specifies the two vertices of that edge)

I tried and actually draw some example graphs for $\phi$ and I can conclude that the graph is NOT complete. If it was I could use the theorem that says that a complete graph has $\frac{(n-1)!}{2}$ Hamiltonian cycles.

What can I do now since it's not a complete graph?

• I think the problem statement has a few typos. Presuming that we're working with undirected graphs, edges $a,b$ and $e,f$ are identical which must be a typo. I think they meant $b=\{1,3\}$ and $e=\{2,4\}$ which would indeed give us a complete graph (here $K_4$) – Prasun Biswas Dec 21 '17 at 17:48
• That would also make sense but this exercise is not for a complete graph. The information they give is correct – Amateur Mathematician Dec 21 '17 at 18:08

If you draw the graph you see the following picture

Recall that a Hamiltonian cycle is a cycle that visits each vertex. In this case there are 4 ways to do this:

• We start at vertex 1 and move to vertex 2 with two edges to choose from: a and b

• from vertex 2 there is only one way to get to vertex 3: d

• from vertex 3 there are two ways to get to vertex 4: e and f

• from vertex 4 there is just one way to get to vertex 1: c

Thus we have 4 paths which depend on the choice we make between a and b and between e and f:

$$adec,\quad adfc,\quad bdec,\quad bdfc.$$

The only possible issue is to make sure that $1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 1$ is the only cyclic order we can visit the vertices in. This should be clear from the picture.