edited by
1,787 views

2 Answers

Best answer
4 votes
4 votes
In any complete graph Kn, number of cycles possible of m vertices are:

nCm (m-1)!/2

Now, for maximum number of cycles, we should count all cycles possible and we know to make cycle we  need minimum 3 vertices,

Maximum = nC3 + nC4 (3!/2) + nC5 (4!/2) +....+ nCn (n-1)!/2

Is my calculation is right or wrong let me know!
selected by
1 votes
1 votes

I think the question is enquiring about the number of maximum length cycles in a complete graph. Maximum length cycle is nothing but a hamilton cycle. Since the the graph is unlabelled , so the order of vertices in the cycle doesn't matter. 

Answer:- 1
 

If the same question is asked for a labelled graph then the answer would be (n-1)!/2.
 

If the question is about the maximum number of cycles in a complete labelled graph then the answer will be:- 
  where k is the length of the cycle.

If the question is about the maximum number of distinct cycles in an unlabelled complete graph , then the answer will be:-  

edited by

Related questions

0 votes
0 votes
0 answers
1
iarnav asked Apr 19, 2018
398 views
Some say answer is 2n and someplace else it's been told 2n-1-1. So, what's the corrent one?
0 votes
0 votes
1 answer
3
admin asked Mar 30, 2020
2,318 views
Let $G$ be a complete undirected graph on $8$ vertices. If vertices of $G$ are labelled, then the number of distinct cycles of length $5$ in $G$ is equal to:$15$$30$$56$$...
1 votes
1 votes
1 answer
4
Rahul Jain25 asked Oct 10, 2016
363 views