(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?

  • $\begingroup$ 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$) $\endgroup$ – Prasun Biswas Dec 21 '17 at 17:48
  • $\begingroup$ That would also make sense but this exercise is not for a complete graph. The information they give is correct $\endgroup$ – Amateur Mathematician Dec 21 '17 at 18:08

If you draw the graph you see the following picture

4 cycle with 2 opposing double edges

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.