1
$\begingroup$

Question

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

$\endgroup$
2
  • $\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
    Commented Dec 21, 2017 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$
    – Numbermind
    Commented Dec 21, 2017 at 18:08

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .