A GATE graph question almost never asks you to define a graph. It asks how the graph is stored, what the traversal actually computes, and what that pairing costs. An adjacency matrix pushes depth-first search to Θ(n²), because every neighbour lookup scans a full row of n entries; an adjacency list keeps the same traversal at Θ(n + m). Breadth-first search on an unweighted graph hands you single-source shortest paths for free, while depth-first search hands you the component count, one search tree per component. Ten previous-year GATE problems follow, each tagged with its year, and each answer links to the full worked solution inside the course. Attempt one before you read its answer. If a traversal itself feels shaky, the Graph Algorithms: BFS, DFS and Shortest Paths deep dive and the Data Structures learn module rebuild them from scratch.
Representations and graph basics
Q1. The most appropriate matching for the pairs, depth-first search, breadth-first search and sorting against heap, queue and stack, is (GATE 2000)
(a) DFS-heap, BFS-queue, Sorting-stack
(b) DFS-stack, BFS-heap, Sorting-queue
(c) DFS-stack, BFS-queue, Sorting-heap
(d) DFS-queue, BFS-stack, Sorting-heap
Answer: (c). Depth-first search dives along a path and backtracks, which is exactly stack behaviour, whether an explicit stack or the recursion stack. Breadth-first search fans out level by level, which needs a queue. Heapsort is the sorting method that leans on a heap, so the clean matching is DFS-stack, BFS-queue, Sorting-heap (see the full solution).
Q2. For a simple undirected graph with adjacency matrix A, the number of triangles (3-cycles) equals the trace of (GATE 2022)
(a) A³
(b) A³ divided by 2
(c) A³ divided by 3
(d) A³ divided by 6
Answer: (d). The diagonal entry (A³) at position i counts closed walks of length three starting and ending at vertex i, and the trace sums these over all vertices. Each triangle is counted once for every choice of starting vertex (three of them) and each of two directions, so every triangle is counted six times. Dividing the trace of A³ by 6 recovers the true triangle count (see the full solution).
Q3. For undirected graphs, consider α: does G have an independent set of size |V| − 4, and β: does G have an independent set of size 5. Which is true? (GATE 2005)
(a) α is in P and β is NP-complete
(b) α is NP-complete and β is in P
(c) Both α and β are NP-complete
(d) Both α and β are in P
Answer: (d). Independent set is hard only when the target size grows with the graph; here both sizes are effectively fixed. For β, checking every 5-vertex subset takes O(n⁵), which is polynomial. For α, an independent set of size |V| − 4 exists exactly when a vertex cover of size 4 exists, and that too is checkable in polynomial time, so both problems are in P (see the full solution).
Q4. In an adjacency-list representation of an undirected graph, each edge has two entries that are twins of each other. With |V| = n and |E| = m, the time to set a twin pointer in every entry, most efficiently, is (GATE 2016)
(a) Θ(n²)
(b) Θ(n + m)
(c) Θ(m²)
(d) Θ(n⁴)
Answer: (b) Θ(n + m). Walk through all 2m adjacency-list entries once, and for each entry representing edge (u, v) compute the unordered key (min(u, v), max(u, v)). A hash table keyed on that pair links the two entries of every edge the moment its second copy appears. The whole pass is linear in the size of the structure, Θ(n + m) (see the full solution).
BFS and DFS
Q5. Level-order traversal of a rooted tree, starting from the root, is done by performing (GATE 2004)
(a) preorder traversal
(b) inorder traversal
(c) depth first search
(d) breadth first search
Answer: (d). Visiting a tree one level at a time is exactly breadth-first search: enqueue the root, then repeatedly dequeue a node, visit it, and enqueue its children. The queue guarantees that all nodes at depth d are seen before any node at depth d+1. The depth-first orders (preorder, inorder) instead plunge down one branch first, so they are not level-order (see the full solution).
Q6. Consider the tree arcs of a BFS traversal from a source W in an unweighted, connected, undirected graph. The tree T formed by these arcs is a structure for computing (GATE 2014)
(a) the shortest path between every pair of vertices
(b) the shortest path from W to every vertex in the graph
(c) the shortest paths from W only to the leaves of T
(d) the longest path in the graph
Answer: (b). BFS discovers vertices in layers by their distance in edges from W, so a vertex first reached at layer d is genuinely at distance d. The parent pointers set during discovery form a tree whose root-to-vertex path is a shortest path from W. That gives single-source shortest paths from W to every vertex, not all-pairs and not just the leaves (see the full solution).
Q7. Let G have n vertices and m edges. What is the tightest upper bound on the running time of depth-first search when G is stored as an adjacency matrix? (GATE 2014)
(a) Θ(n)
(b) Θ(n + m)
(c) Θ(n²)
(d) Θ(m²)
Answer: (c) Θ(n²). With an adjacency matrix, finding the neighbours of a vertex means scanning its entire row of n entries. DFS visits every vertex once, and each visit costs Θ(n) for that row scan, so the total is Θ(n²). The familiar Θ(n + m) bound applies only to adjacency lists, where you touch just the edges that exist (see the full solution).
Connected components and strong connectivity
Q8. In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is (GATE 2005)
(a) k
(b) k + 1
(c) n − k − 1
(d) n − k
Answer: (d) n − k. Each connected component of size v contributes exactly v − 1 tree edges, because a DFS tree over v vertices has v − 1 edges. Summing across c components, the total tree edges are k = n − c. Rearranging gives the component count c = n − k, independent of how the edges are distributed (see the full solution).
Q9. The most efficient algorithm for finding the number of connected components in an undirected graph with n vertices and m edges has time complexity (GATE 2008)
(a) Θ(n)
(b) Θ(m)
(c) Θ(m + n)
(d) Θ(mn)
Answer: (c) Θ(m + n). Run BFS or DFS on an adjacency list: start a fresh traversal from each still-unvisited vertex, and each such traversal marks one whole component. Every vertex is processed once and every edge examined a constant number of times, so the total work is Θ(n + m). You cannot do better, since you must at least look at every vertex and edge (see the full solution).
Q10. Let G = (V, E) be a directed graph. Which one of the following graphs has the same strongly connected components as G? (GATE 2014)
(a) G1 with edge set { (u, v) | (u, v) ∉ E }
(b) G2 with edge set { (u, v) | (v, u) ∈ E }
(c) G3 with an edge whenever there is a path of length at most 2 in G
(d) G4 on only the non-isolated vertices of G
Answer: (b). Strong connectivity is about mutual reachability: u and v share a component when a directed path runs each way. Reversing every edge, which is what G2 does, turns a path u to v into a path v to u and vice versa, and reversing a second time returns the original graph, so G2 and G have exactly the same components. G1 keeps only the pairs that were not edges, which scrambles reachability outright, and G4 drops the isolated vertices, each of which is a strongly connected component in its own right, so its component list is short by exactly those. G3 is the distractor worth pausing on: every shortcut edge it adds runs along a path that already existed, so the safe answer is the one whose preservation is guaranteed by construction in both directions, G2 (see the full solution).
How graphs are examined
GATE's graph questions have clustered in the same three places from 2000 through 2022. Storage and basics come first: which structure powers which traversal, how the storage choice fixes the running time, and when a size-bounded subset question stays polynomial instead of turning NP-complete. Traversals come next, and the examiner cares about what they compute rather than how you code them, with two facts doing most of the work: BFS on an unweighted graph gives single-source shortest paths, and an adjacency matrix forces Θ(n²) on DFS. Connectivity closes it out on two small invariants: a component of v vertices contributes exactly v − 1 tree edges, so n vertices and k tree edges mean n − k components, and reversing every edge leaves the strongly connected components untouched.
If a question exposed a gap, it is a concept gap, not a volume one. Rebuild the traversals through the GATE CS Exam category, then drill the full previous-year sets inside GATE Guidance by Sanchit Sir. Solve, review the ones you missed, and return to this set a week later; the second pass is where the marks get locked in.
