Graphs are the highest-value structure in the Data Structures paper, and GATE tests a compact core: how a graph is stored, what BFS and DFS actually compute, the running times each representation forces, and how to reason about components and strong connectivity. Below are 10 solved MCQs from KnowledgeGate's published question bank, every one a previous-year GATE problem with the year marked. Attempt each before the explanation, which is deliberately short. A note on the deep links: each question here carries a GATE tag inside the course, so we link its exact solved page for the full working. If the underlying idea slips, the Graph Algorithms: BFS, DFS and Shortest Paths deep dive and the Data Structures learn module rebuild the traversals from scratch.
Graph representations
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 solved page).
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 solved page).
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 solved page).
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 solved page).
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 solved page).
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 solved page).
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 solved page).
Topological sort and 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 solved page).
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 solved page).
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, so mutual reachability is preserved exactly. The complement and the path-squaring graphs both change which pairs can reach each other, so they alter the components (see the solved page).
How graphs are examined
The set mirrors GATE's steady pattern. The representation block (Q1 to Q4) rewards knowing which structure powers which traversal and how the storage choice fixes the running time. The traversal block (Q5 to Q7) is about what BFS and DFS actually compute, with the standout fact that BFS on an unweighted graph yields single-source shortest paths, and that an adjacency matrix forces Θ(n²) on DFS. The connectivity block (Q8 to Q10) turns on counting tree edges per component and the reversal invariance of strongly connected components.
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.