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

PYQ GATE 2018

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 107 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…