retagged by
34,603 views
111 votes
111 votes

Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to

  1. $15$
  2. $30$
  3. $90$
  4. $360$
retagged by

9 Answers

Best answer
190 votes
190 votes
From $6$ vertices we can select $4$ distinct vertices in $^{6}C_{4} = 15$ ways.
Now, with $4$ vertices, we can form only $3$ distinct cycles. [See below]
So, total no. of distinct cycles of length $4 = 15\times 3 = 45.$

No. of cyclic permutations of n objects $=\left(n-1\right)!$ and for $n = 4,$ we get $3! = 6$ ways. But number of distinct cycles in a graph is exactly half the number of cyclic permutations as there is no left/right ordering in a graph. For example $a - b - c - d$ and $a - d - c - b$ are different permutations but in a graph they form the same cycle.

Since, $45$ was not in the choice, marks were given to all in GATE.
edited by
103 votes
103 votes

There can be total 6C4 ways to pick 4 vertices from 6. The value of 6C4 is 15.

Note that the given graph is complete so any 4 vertices can form a cycle.

There can be 6 different cycle with 4 vertices. For example, consider 4 vertices as a, b, c and d. The three distinct cycles are

cycles should be like this
(a, b, c, d,a)
(a, b, d, c,a)
(a, c, b, d,a)
(a, c, d, b,a)
(a, d, b, c,a)
(a, d, c, b,a)

and

(a, b, c, d,a) and (a, d, c, b,a)
(a, b, d, c,a) and (a, c, d, b,a)
(a, c, b, d,a) and (a, d, b, c,a)
are same cycles.

So total number of distinct cycles is (15*3) = 45.

The answer is 45.

44 votes
44 votes

Hence the answer need correction :)

27 votes
27 votes

This question asks for Hamiltonian cycles.

The corresponding formulae for complete graphs are:-

  • undirected: $(n-1)!/2$
     
  • directed: $(n-1)!$
     
  • The above two are applicable only when graph is labelled. If unlabelled, then we can't distinguish between cycles. Let all the nodes be labelled A (it is equivalent to them being unlabelled)
    A —> A —> A —> A
    A —> A —> A —> A
    Do you see any difference? Me neither :P

    Hence, when the graph is unlabelled, hamiltonian cycles possible are $1$ — no matter the type of edges (directed or undirected)

 


The question pertains to the first formula.

Ways to select 4 vertices out of 6 = ${^6C_4}=15$ (In a complete graph, each 4 vertices will give a 4 edged cycle)

Hamiltonian cycles possible on each such 4 vertices = $(4-1)!/2=3$

So, total = $15*3=45$

(Answer)


What if the graph was unlabelled?

By the third formula here, the answer would be 1. We don't care if the edges are directed or undirected; if the graph is unlabelled, hamiltonian cycles possible will always be 1.


What if the edges were directed?

By the second formula here, it'll be $15*(4-1)!$

Which is equal to $90$

 

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

And to understand from where do $(n-1)!/2$ and $(n-1)!$ come from, give this a read. Won't take more than 5 minutes.

Answer:

Related questions

59 votes
59 votes
5 answers
1
29 votes
29 votes
4 answers
2
Arjun asked Sep 25, 2014
10,970 views
Which of the following graphs is isomorphic to
26 votes
26 votes
3 answers
3
gatecse asked Aug 5, 2014
9,967 views
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the...
45 votes
45 votes
3 answers
4
gatecse asked Aug 21, 2014
11,807 views
Which one of the following is NOT logically equivalent to $¬∃x(∀ y (α)∧∀z(β ))$ ?$∀ x(∃ z(¬β )→∀ y(α))$$∀x(∀ z(β )→∃ y(¬α))$$∀x(∀ y(�...