GATE 2012 CS (CS1) – Question 48

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · MTA

A complete undirected graph has six labelled vertices. How many distinct cycles of length four does it contain?

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: MTA

Explanation

The final key awards marks to all. Under the usual undirected-cycle convention, choose four vertices in $\binom64=15$ ways. Each set has (4−1)!/2=3 cycles after identifying rotations and reversal, giving 45. None of the options is 45. Counting opposite orientations separately gives 90, explaining the alternative convention but not a unique undirected answer.

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

GATE 2013 CS (CS1) Q35 – For undirected graphs, P: The number of odd-degree vertices is even. Q: The sum of all…
GATE 2013 CS (CS1) Q36 – The line graph L(G) has one vertex per edge of simple G, and joins vertices iff their G…
GATE 2011 CS (CS1) Q27 – The drawings show complete graph K₄ and cube graph Q₃. Which is true?
GATE 2010 CS (CS1) Q11 – For graph G=(V,E), let (G)= di dd, where i d counts vertices of degree d. If different…
GATE 2010 CS (CS1) Q38 – Which sequences cannot be degree sequences of simple graphs? I: 7,6,5,4,4,3,2,1 II:…
GATE 2015 CS (CS2) Q61 – A self-complementary graph is isomorphic to its complement. What must its vertex count n…

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →