High yield ●●●

🕸️ Graph Algorithms

Why it matters: The largest algorithm topic: traversals, MST, shortest paths and topological order are asked in several questions per paper.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 7 done.

Formulas

Edges
undirected simple: 0 ≤ E ≤ V(V − 1)/2; connected: E ≥ V − 1; directed simple: E ≤ V(V − 1); Σ deg = 2E
BFS / DFS
O(V + E) with adjacency lists; O(V²) with an adjacency matrix
MST
Kruskal O(E log E); Prim O(E log V) heap, O(V²) array; MST has V − 1 edges
Shortest paths
Dijkstra O((V + E) log V); Bellman-Ford O(VE); Floyd-Warshall Θ(V³)
Topological sort
O(V + E); exists iff the graph is a DAG
Edge classes (directed DFS)
back edge ⇔ cycle; forward / cross edges go to a finished vertex

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Minimum spanning tree: weight, uniqueness, which edges
Run Kruskal by hand; decide whether the MST is unique, whether a given edge must be in it.
★★★
Dijkstra / shortest path order or distance
Order in which vertices are finalised, and the final distance of a vertex; effect of negative edges.
★★★
BFS / DFS order, time complexity, applications
Visit order for a given graph, finishing times, cycle detection.
★★★
Topological orders of a DAG
Count or list valid orders, find which sequence is valid.
★★★
Graph facts (degrees, edges, connectivity)
Maximum edges, number of components, handshake lemma.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

35 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

35 questions · 0 correct of 0 attempted · marks 0 / 57

Year:
GATE 2025 CS1 · Q18MCQ1 mark
Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. For any two vertices u and v, let d1(u, v) and d2(u, v) be the shortest distances between u and v in G and T, respectively. Which ONE of the options is CORRECT for all possible G, T, u and v?
GATE 2025 CS2 · Q29MSQ1 mark
Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

One or more options may be correct. Select all that apply, then submit.

GATE 2025 CS2 · Q37MCQ2 marks
Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant α is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?
GATE 2025 CS1 · Q43MCQ2 marks
Let 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 vertices u and v in V. Let the maximum value of d(u, v), u, v ∈ V such that u ≠ v, be 30. Let T be any breadth-first-search tree of G. Which ONE of the given options is CORRECT for every such graph G?
GATE 2024 CS1 · Q34NAT1 mark
The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is ______.
GATE 2024 CS1 · Q45MSQ2 marks
Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. Which of the following statements is/are TRUE for every such graph G and tree T?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS2 · Q51MSQ2 marks
Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in G has even weight. Which of the following statements is/are TRUE for every such graph G?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS1 · Q60NAT2 marks
The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected components in G is ______.
GATE 2023 · Q55MSQ2 marks
Let G be a simple, finite, undirected graph with vertex set {v1, …, vn}. Let Δ(G) denote the maximum degree of G and let N = {1, 2, …} denote the set of all possible colors. Color the vertices of G using the following greedy strategy: for i = 1, …, n: color(vi) ← min{ j ∈ N : no neighbour of vi is colored j }. Which of the following statements is/are TRUE?

One or more options may be correct. Select all that apply, then submit.

GATE 2023 · Q56NAT2 marks
Let U = {1, 2, 3}. Let 2U denote the powerset of U. Consider an undirected graph G whose vertex set is 2U. For any A, B ∈ 2U, (A, B) is an edge in G if and only if (i) A ≠ B, and (ii) either A ⊊ B or B ⊊ A. For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by B(A). If ∅ denotes the empty set, then the cardinality of B(∅) is ______.
GATE 2022 · Q30NAT1 mark
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ______.
GATE 2022 · Q37MCQ2 marks
Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of
GATE 2022 · Q49MSQ2 marks
Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?

One or more options may be correct. Select all that apply, then submit.

GATE 2022 · Q52MSQ2 marks
Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 1 · Q16NAT1 mark
In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______.
GATE 2021 Set 1 · Q17NAT1 mark
Consider the following undirected graph with edge weights as shown. The graph is a 3 × 3 grid of nine vertices. Top row: edges 0.1 and 0.1. Top-to-middle verticals: 0.9, 0.9, 0.9. Middle row: edges 0.1 and 0.9. Middle-to-bottom verticals: 0.1, 0.1, 0.1. Bottom row: edges 0.9 and 0.1. The number of minimum-weight spanning trees of the graph is ______.
GATE 2021 Set 1 · Q36MCQ2 marks
Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as diam(G) = max over u, v ∈ V of {the length of the shortest path between u and v}. Let M be the adjacency matrix of G. Define graph G2 on the same set of vertices with adjacency matrix N, where Nij = 1 if Mij > 0 or Pij > 0, where P = M², and 0 otherwise. Which one of the following statements is true?
GATE 2021 Set 1 · Q41MSQ2 marks
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?

One or more options may be correct. Select all that apply, then submit.

GATE 2020 · Q31MCQ2 marks
Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u, v) ∈ V × V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is
GATE 2020 · Q40MCQ2 marks
Let G = (V, E) be a directed, weighted graph with weight function w: E → ℝ. For some function f: V → ℝ, for each edge (u, v) ∈ E, define w'(u, v) as w(u, v) + f(u) − f(v). Which one of the options completes the following sentence so that it is TRUE? "The shortest paths in G under w are shortest paths under w' too, ______."
GATE 2020 · Q49NAT2 marks
Consider a graph G = (V, E), where V = {v1, v2, …, v100}, E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i − j|. The weight of minimum spanning tree of G is ______.
GATE 2019 Set 2 · Q38MCQ2 marks
Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut. Which of the above two statements is/are TRUE?
GATE 2018 · Q30MCQ2 marks
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.
(I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u, v) of G, if u is at depth i and v is at depth j in TB, then |i − j| = 1. Which of the statements above must necessarily be true?
GATE 2018 · Q43NAT2 marks
Let G 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 u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y + 10z = ______.
GATE 2017 Set 1 · Q20NAT1 mark
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is ______.
GATE 2017 Set 1 · Q26MCQ2 marks
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:
(I) Minimum Spanning Tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique. Which of the above statements is/are necessarily true?
GATE 2016 Set 1 · Q14MCQ1 mark
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change. Q: Shortest path between any pair of vertices does not change.
GATE 2016 Set 1 · Q38NAT2 marks
Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the entry Wij in the matrix W = [[0, 2, 8, 5], [2, 0, 5, 8], [8, 5, 0, x], [5, 8, x, 0]]. The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ______.
GATE 2016 Set 1 · Q39NAT2 marks
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is ______.
GATE 2016 Set 1 · Q40MCQ2 marks
G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE? I. If e is the lightest edge of some cycle in G, then every MST of G includes e. II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e.
GATE 2014 Set 1 · Q3MCQ1 mark
Let G = (V, E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?
GATE 2014 Set 1 · Q11MCQ1 mark
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
GATE 2013 Code A · Q19MCQ1 mark
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
GATE 2013 Code A · Q25MCQ1 mark
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.
GATE 2012 Code A · Q17MCQ1 mark
Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to

Common traps

Dijkstra can fail with a negative edge even when there is no negative cycle.
Equal edge weights can give several different MSTs, but all have the same total weight.
Time depends on the representation: matrix BFS is O(V²), not O(V + E).
DFS in an undirected graph: an edge to the parent is not a back edge.