Dark Mode

36 votes

Best answer

The number of different Hamiltonian cycles in a complete undirected **labeled **graph on $n$ vertices is $(n − 1)! / 2$.

Ref : https://en.wikipedia.org/wiki/Hamiltonian_path

If the graph is unlabeled number of different Hamiltonian cycles become $1.$

Since the question does not mention whether the graph is labeled or not, answer can be either (C) or (D).

Official answer key is (D) or (C)

4 votes

From any vertex we have n−1 edges to choose from first vertex, n−2 edges to choose from second vertex, n−3 to choose from the third and so on. These being independent choices, we get (n−1)! possible number of choices.

Each Hamiltonian circuit has been counted twice (in reverse direction of each other like these: A→B→C→A and A→C→B→A).

**Number of distinct not edge disjoint Hamiltonian circuits in complete graph Kn is (n−1)!/2**