Graph Traversal MCQs: 12 Solved Questions on Walks, Paths, Trails, Circuits and Connectivity

Graph questions switch vocabulary and proof method without warning. A route can be a walk but not a trail, while one edge-count threshold can decide connectivity. Start each problem by naming the decisive invariant: repeated edge, repeated vertex, closure, residue class, mutual reachability or extremal edge count. For Euler paths, colouring and trees as a mixed review, use Graph Theory MCQs. For cut vertices, edge cuts and the connectivity inequalities, use Cut Set and Connectivity MCQs; Questions 2 and 9-11 here instead connect route vocabulary to minimum and maximum edge invariants.

Walk, trail, path, circuit and connectivity: the working vocabulary

A walk is a vertex-edge sequence that may repeat vertices and edges. A trail repeats no edge; a path repeats no vertex. A closed trail is a circuit. A cycle is a closed path except for its repeated start and end. Directed steps must follow their arrows. A graph is connected when every vertex pair has a path; a directed graph is strongly connected when every ordered pair is mutually reachable.

For V={A,B,C,D,E} and E={AB,BC,CA,CD,DE}, A-B-C-A-B is a walk but not a trail because AB repeats. D-C-A-B-C is a trail but not a path because C repeats. E-D-C-B-A is a path. A-B-C-A is a circuit and cycle. Bridge CD connects triangle {A,B,C} to chain D-E; deleting it leaves components {A,B,C} and {D,E}.

Audit five things: direction, repeated edges, repeated vertices, whether start equals finish, and whether the claim concerns one route or all-pairs reachability.

Questions 1-2: recognise traversal order and biconnectivity

Question 1: Identify the ordering on a directed acyclic graph

Coal India 2017

A ______ takes a directed ______ graph G and produces a linear ordering of all its vertices such that for every directed edge (v, w), the vertex v comes before the vertex w in the ordering.

• A. breadth first search; acyclic

• B. topological sort; acyclic

• C. breadth first search; cyclic

• D. topological sort; cyclic

Correct answer: B. A topological sort puts v before w for every v->w and requires a DAG. For A->B, A->C, B->D and C->D, both A,B,C,D and A,C,B,D work; a directed cycle makes a vertex precede itself. Use Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step for full exploration traces; unlike BFS and DFS orders, a topological order must satisfy every precedence edge.

Question 2: Name a connected graph with no articulation vertex

Coal India 2017

If a connected graph G does not contain any vertex whose removal disconnects the rest of the graph, then G is called:

• A. Biconnected graph

• B. Separable graph

• C. Forest

• D. Digraph

Correct answer: A. Deleting an articulation (cut) vertex increases the component count; a connected graph without one is biconnected. Deleting any C4 vertex leaves a connected three-vertex path, while deleting B from A-B-C separates A and C.

Questions 3-4: maximise disconnected edges and count grid paths

Question 3: Maximum edges in a disconnected 10-vertex graph

GATE 2022

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.

Compute the maximum edge count before checking the answer.

Correct answer: 36. Isolate one vertex and form K9: C(9,2)=9x8/2=36. A K8 + K2 split gives 28+1=29; other splits lose more cross-pairs.

Question 4: Count monotone paths from (0, 0) to (10, 10)

GATE 2007

Suppose that a robot is placed on the Cartesian plane. At each step, it is allowed to move either one unit up or one unit right. That is, if the robot is at position (i, j), then it can move to either (i + 1, j) or (i, j + 1).

How many distinct paths are there for the robot to reach the point (10, 10) starting from the initial position (0, 0)?

• A. C(20, 10)

• B. 2^20

• C. 2^10

• D. None of the above

Correct answer: A. Each route has ten right and ten up moves. Choose ten of 20 slots for right moves: C(20,10)=20!/(10!10!)=184756. 2^20 also counts strings without ten of each move.

Questions 5-6: derive components from arithmetic and arrows

Question 5: Count connected components when edges differ by 8 or 12

GATE 1997

Let G be the graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if |i-j|=8 or |i-j|=12. The number of connected components in G is

• A. 8

• B. 4

• C. 12

• D. 25

Correct answer: B. Since gcd(8,12)=4, edges preserve residue modulo 4, giving at least four components. Divide one class by 4: jumps become 2 and 3 across 25 positions. Positions 0,1,2,3 connect via 0-3-1 and 0-2; every later m+1 joins m-1 by 2. Each class is therefore connected: exactly four components.

Question 6: Read the strongly connected component from a directed figure

ISRO 2008

Identify a valid strong component in the directed graph.

Which of the following is a valid strong component?

• A. a, c, d

• B. a, b, d

• C. b, c, d

• D. a, b, c

Correct answer: D. Cycle a->b->c->a makes a,b,c mutually reachable. Arrows enter d from a,c, but none returns, so the strong component is {a,b,c}.

Questions 7-8: relate paths to trails and trace the longest flow-graph path

Question 7: Relate paths and trails in a simple graph

Capgemini 2024

Which of the following statements for a simple graph is correct?

• A. Every path is a trail

• B. Every trail is a path

• C. Every trail is a path and every path is a trail

• D. Paths and trails have no relation

Correct answer: A. A path never repeats a vertex, so it cannot traverse the same edge twice; every path therefore satisfies the no-repeated-edge rule for a trail. The converse fails on triangle A-B-C-A: no edge repeats, but vertex A does, making it a trail rather than a path.

Question 8: Count nodes on the longest independent path in a flow graph

UGC NET 2019

Consider the flow graph F with entry node (1) and exit node (11).

How many nodes are there in the longest independent path?

• A. 6

• B. 7

• C. 8

• D. 9

Correct answer: C. Expand grouped labels. Route 1->2->3->6->7->9->10->11 has eight nodes; replacing 7 by 8 ties it. Branches 7 and 8 merge at 9; a simple path cannot include both. Maximum: 8.

Questions 9-10: minimum connected edges and maximum disconnected edges

Question 9: Minimum edges in a connected n-vertex graph

UGC NET 2010

The minimum number of edges in a connected graph with ‘n’ vertices is equal to

• A. n(n - 1)

• B. n(n - 1)/2

• C. n^2

• D. n - 1

Correct answer: D. Every connected graph contains a spanning tree, and every n-vertex tree has n-1 edges. Fewer cannot connect all vertices; path P_n attains this. n(n-1)/2 instead counts complete-graph edges.

Question 10: Maximum edges while 100 vertices remain disconnected

UGC NET 2013

Consider an undirected graph G with 100 nodes. The maximum number of edges to be included in G so that the graph is not connected is

• A. 2451

• B. 4950

• C. 4851

• D. 9900

Correct answer: C. Isolate one node and form K99: C(99,2)=99x98/2=4851. The next edge joins the isolate to the clique and connects the graph. Thus 4851 is maximal.

Questions 11-12: connectivity thresholds and traversal-algorithm labels

Question 11: Choose the edge threshold that guarantees connectivity

UGC NET 2013

A simple graph G with n vertices is connected if the graph has:

• A. (n - 1)(n - 2)/2 edges

• B. More than (n - 1)(n - 2)/2 edges

• C. Less than (n - 1)(n - 2)/2 edges

• D. sum from i = 1 to k of C(n_i, 2) edges

Correct answer: B. The densest disconnected graph, K_(n-1) plus an isolate, has C(n-1,2)=(n-1)(n-2)/2 edges. Equality fails; any larger count forces connectivity.

Question 12: Distinguish graph traversals from algorithmic paradigms

BPSC 2024

Which of the following is NOT a graph traversal algorithm?

• A. Greedy

• B. Divide and Conquer

• C. Dynamic Programming

• D. More than one of the above

• E. None of the above

Correct answer: D. BFS and DFS are traversals; greedy, divide and conquer, and dynamic programming are design paradigms. A, B and C all fit, so the correct choice is more than one of the above.

Answer map, recurring traps and the next practice step

Answer key: 1-B; 2-A; 3-36; 4-A; 5-B; 6-D; 7-A; 8-C; 9-D; 10-C; 11-B; 12-D

Redraw the directed graphs in Questions 6 and 8 from memory, then recompute Questions 3, 4, 5, 10 and 11 without the answer map. Finish by classifying each route in the opening example as a walk, trail, path or circuit and naming the exact rule that separates it from the next category.

Classify a route by repeated edges, repeated vertices and closure. In directed graphs, follow every arrow and require mutual reachability for a strong component. For connectivity bounds, use a tree for the minimum connected count or K_(n-1) plus an isolate for the maximum disconnected count. If the concepts feel weak, work through GATE Guidance by Sanchit Sir, stating each invariant before you calculate.