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, _____.
GATE CS 2018 (Forenoon) — Question 53
Discrete MathematicsGraph Theory (Connectivity, Paths, Cycles, Trees)NAT2 marksHard
A GATE question every morning
One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.
More on Graph Theory (Connectivity, Paths, Cycles, Trees)
- GATE CS 2026 (Forenoon) · Q55An undirected, unweighted, simple graph G(V, E) is said to be 2-colorable if there exists a function c : V \ 0, 1\ such that for every (u,…
- GATE CS 2026 (Afternoon) · Q36Consider a complete graph K n with n vertices ( n > 4 ). Note that multiple spanning trees can be constructed over K n . Each of these span…
- GATE CS 2025 (Forenoon) · Q43Let G(V, E) be an undirected and unweighted graph with 100 vertices. Let d(u, v) denote the number of edges in a shortest path between vert…
- GATE CS 2024 (Forenoon) · Q34The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is .
- GATE CS 2024 (Afternoon) · Q17Let A be the adjacency matrix of a simple undirected graph G . Suppose A is its own inverse. Which one of the following statements is alway…
- GATE CS 2024 (Afternoon) · Q51Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in G has even we…

