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

14 votes
14 votes

Answer would be 6C4 * 4! /(4*2) =45

Explanation:

Number of ways to choose 4 vertices = 6C4
Total number of cycles from a particular set of 4 vertices = 4!/(4*2) (since the same cycle can start from different vertices and go in both directions)

edited by
9 votes
9 votes

From 6 vertices we select 4 vertices in 6C4 = 15 ways.
Now, with these 4 vertices, we can form only 3 distinct cycles.

How ? Since, all 4 vertices have adjacent edge to other 3 choosen vertices, i.e. total 6 edges. Now every cycle is 2-regular. Therefore, every vertice is adjacent to 2 other vertices. So, for first vertex, we have 3 choices to choose 2 adjacent vertices out of 3 vertices. Now, we have drawn 2 lines of cycle and selected 3 vertices out of 4. For last, we have no choice, since first vertex already rejected it to be its adjacent. so, it will join to other vertices.

Hence 15*3=45 is the answer.

8 votes
8 votes
lets discuss for general graph if $k_{n}$ is complete graph then to select cycle of m length we require $\binom{n}{m}$ after selecting each cycle we to also arrange them in different way so it takes (m-1)!/2 , because in order to arrange in cycle , so total cycle will be $\binom{n}{m}$(m-1)!/2

therefore for 6 vertices we required no of cycle of length 4 = (6c4)(4-1)!/2=45
edited by
0 votes
0 votes

Answer : 45

Total no. of cycles of length 'k' in a complete graph of n vertices = [ nCk ]*(k-1)!/2

so, 6C4 * (4-1)!/2

=15*3 = 45

Answer:

Related questions

59 votes
59 votes
5 answers
1
29 votes
29 votes
4 answers
2
Arjun asked Sep 25, 2014
10,971 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(�...