Let \(G\) be a graph with 100! vertices, with each vertex labelled by a…
GATE · 2018 · CS · Computer Science & IT
Let 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 , and 𝑧 denote the number of connected components in . Then, 𝑦 + 10𝑧 = _____.
Attempted by 97 students.
Sign up free to check your answer
Sign up freeLoading lesson…