@JAINchiNMay Can you show 1 eg, where it contradicts? I couldn't find any.

Dark Mode

28,898 views

101 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

- $15$
- $30$
- $90$
- $360$

edited
Nov 5, 2022
by Abhrajyoti00

@JAINchiNMay Look at this unlabelled undirected complete graph of 6 vertices. Any cycle of length 4 you take, there's only 1 distinct because every cycle is unlabelled.

1

181 votes

Best answer

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.

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.

95 votes

There can be total ^{6}C_{4} ways to pick 4 vertices from 6. The value of ^{6}C_{4} 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.**

38 votes

0

24 votes

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)

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.

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.