Let \(G\) be a graph with 100! vertices, with each vertex labelled by a…

GATE · 2018 · CS · Computer Science & IT

Let GG be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, … , 100. There is an edge between vertices 𝑢 and 𝑣 if and only if the label of 𝑢 can be obtained by swapping two adjacent numbers in the label of 𝑣. Let 𝑦 denote the degree of a vertex in GG, and 𝑧 denote the number of connected components in GG. Then, 𝑦 + 10𝑧 = _____.

Attempted by 97 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…