Graphs MCQs in Data Structure
Graphs MCQs with Solutions
1.
A graph with n vertices and n−1 edges, with all vertices connected, is called:
A. Tree
B. Complete graph
C. Cycle graph
D. Directed graph
Answer: A
Solution:
A connected acyclic graph with n vertices and n−1 edges is a tree.
2.
Number of edges in a complete undirected graph with 10 vertices = ?
A. 45
B. 50
C. 40
D. 55
Answer: A
Solution:
Edges = n(n−1)/2 = 10×9/2 = 45.
3.
A graph having vertices connected in a closed loop is called:
A. Tree
B. Cycle graph
C. DAG
D. Bipartite graph
Answer: B
Solution:
Cycle graph → vertices form a closed loop.
4.
Degree of vertex v in an undirected graph = 5 → number of edges incident on v = ?
A. 4
B. 5
C. 6
D. 3
Answer: B
Solution:
Degree = number of edges incident on the vertex = 5.
5.
A graph with no cycles is called:
A. DAG
B. Tree
C. Simple graph
D. Directed graph
Answer: A
Solution:
A directed acyclic graph (DAG) has no cycles.
6.
Number of edges in a complete directed graph with 7 vertices = ?
A. 21
B. 42
C. 49
D. 14
Answer: B
Solution:
Directed edges = n(n−1) = 7×6 = 42.
7.
DFS traversal of a graph uses:
A. Queue
B. Stack
C. Priority queue
D. Hash table
Answer: B
Solution:
DFS → uses stack (explicit or recursion).
8.
BFS traversal of a graph uses:
A. Stack
B. Queue
C. Priority queue
D. Hash table
Answer: B
Solution:
BFS → uses queue.
9.
A graph containing n vertices and n edges, with one cycle, is called:
A. Tree
B. Graph with cycle
C. Simple graph
D. DAG
Answer: B
Solution:
A connected graph with exactly one cycle → edges = n → contains a single cycle.
10.
Which of the following is true for a bipartite graph?
A. Contains odd cycles
B. Can be colored with 2 colors
C. Complete graph with 4 vertices
D. Has self-loops
Answer: B
Solution:
Bipartite graph → 2-colorable → no odd-length cycles.
11.
Adjacency matrix of a graph with n vertices requires space:
A. O(n)
B. O(n²)
C. O(n log n)
D. O(1)
Answer: B
Solution:
Adjacency matrix → n×n → O(n²) space.
12.
Adjacency list of a graph with V vertices and E edges requires space:
A. O(V²)
B. O(V+E)
C. O(E²)
D. O(V×E)
Answer: B
Solution:
Adjacency list → V nodes + E edges → O(V+E) space.
13.
Graph with all vertices having even degree → Eulerian graph?
A. Yes
B. No
C. Only if connected
D. Only if directed
Answer: C
Solution:
Eulerian graph → connected + all vertices even degree.
14.
Number of edges in a tree with 15 vertices = ?
A. 13
B. 14
C. 15
D. 16
Answer: B
Solution:
Tree → edges = vertices − 1 → 15 − 1 = 14.
15.
Dijkstra’s algorithm works only with:
A. Positive edge weights
B. Negative edge weights
C. Zero weight edges
D. Negative cycles
Answer: A
Solution:
Dijkstra → cannot handle negative edge weights.
16.
Bellman-Ford algorithm can handle:
A. Negative edges
B. Negative cycles
C. Only positive edges
D. No edges
Answer: A
Solution:
Bellman-Ford → handles negative edges but detects negative cycles.
17.
Graph with no self-loops and no multiple edges is called:
A. Simple graph
B. Multi-graph
C. Directed graph
D. Weighted graph
Answer: A
Solution:
Definition of a simple graph.
18.
In-degree of vertex in a directed graph = 3 → number of incoming edges = ?
A. 2
B. 3
C. 4
D. 1
Answer: B
Solution:
In-degree = number of incoming edges.
19.
Out-degree of a vertex = 5 → number of outgoing edges = ?
A. 5
B. 4
C. 6
D. 3
Answer: A
Solution:
Out-degree = number of outgoing edges.
20.
Adjacency matrix for directed graph is symmetric?
A. Always
B. Never
C. Only for undirected graph
D. Only for weighted graph
Answer: C
Solution:
Undirected → symmetric adjacency matrix. Directed → not necessarily symmetric.
21.
DFS starting from vertex u → vertices visited → order depends on:
A. Edge weights
B. Order of adjacency list
C. Vertex degrees
D. Number of edges
Answer: B
Solution:
DFS → stack traversal → order depends on adjacency list order.
22.
BFS finds:
A. Shortest path in unweighted graph
B. Longest path
C. Minimum spanning tree
D. Negative cycle
Answer: A
Solution:
BFS → shortest path in unweighted graph.
23.
Graph with n vertices and no edges → number of connected components = ?
A. 0
B. n
C. 1
D. n−1
Answer: B
Solution:
Each vertex isolated → n connected components.
24.
Complete bipartite graph K3,4 → number of edges = ?
A. 7
B. 12
C. 9
D. 10
Answer: B
Solution:
Edges = m×n = 3×4 = 12.
25.
Graph with odd-length cycle cannot be:
A. Bipartite
B. Eulerian
C. Simple
D. Directed
Answer: A
Solution:
Bipartite → no odd-length cycles.
26.
Topological sort → applicable to:
A. DAG
B. Cyclic graph
C. Undirected graph
D. Weighted graph
Answer: A
Solution:
Topological sort → only DAGs.
27.
Graph with 7 vertices, each vertex connected to all others → edges = ?
A. 21
B. 14
C. 28
D. 42
Answer: A
Solution:
Complete undirected → n(n−1)/2 = 7×6/2 = 21.
28.
Prim’s algorithm → used to find:
A. Minimum spanning tree
B. Shortest path
C. DFS traversal
D. BFS traversal
Answer: A
Solution:
Prim → MST of weighted graph.
29.
Kruskal’s algorithm → time complexity = ?
A. O(E log E)
B. O(V²)
C. O(V+E)
D. O(E)
Answer: A
Solution:
Kruskal → sort edges → O(E log E).
30.
Weighted undirected graph with V vertices → minimum number of edges to connect all vertices = ?
A. V−1
B. V
C. V+1
D. 2V
Answer: A
Solution:
MST → minimum edges = V−1.
31.
DFS → stack-based → time complexity = ?
A. O(V+E)
B. O(V²)
C. O(E²)
D. O(V log V)
Answer: A
Solution:
DFS → visits all vertices & edges → O(V+E).
32.
BFS time complexity = ?
A. O(V+E)
B. O(V²)
C. O(E²)
D. O(V log V)
Answer: A
Solution:
BFS → linear in vertices + edges → O(V+E).
33.
Eulerian cycle exists in undirected graph → condition:
A. All vertices even degree
B. Exactly two vertices odd degree
C. At least one vertex odd degree
D. Any number of vertices odd degree
Answer: A
Solution:
Eulerian cycle → all vertices even degree + connected.
34.
Eulerian path exists if:
A. Exactly 2 vertices odd degree
B. All vertices odd degree
C. No odd-degree vertices
D. Any number of odd-degree vertices
Answer: A
Solution:
Eulerian path → start & end vertices have odd degree.
35.
Graph with negative weight edges → shortest path → cannot use:
A. Dijkstra
B. Bellman-Ford
C. BFS
D. DFS
Answer: A
Solution:
Dijkstra → fails with negative weights.
36.
Strongly connected component → definition:
A. Every vertex reachable from every other vertex
B. Only one vertex reachable
C. No cycles
D. DAG
Answer: A
Solution:
Strongly connected → all vertices mutually reachable.
37.
Number of edges in simple undirected graph with 8 vertices, degree sequence = {3,3,2,2,2,1,1,1} = ?
A. 7
B. 8
C. 9
D. 10
Answer: B
Solution:
Sum of degrees = 16 → edges = sum/2 = 8.
38.
Graph with 6 vertices, adjacency matrix has 12 ones → number of edges = ?
A. 6
B. 12
C. 24
D. 10
Answer: A
Solution:
Undirected → each edge counted twice → edges = 12/2 = 6.
39.
Directed acyclic graph → maximum number of edges with n vertices = ?
A. n(n−1)/2
B. n²
C. n(n+1)/2
D. n
Answer: A
Solution:
DAG → max edges = n(n−1)/2 → topologically sorted vertices.
40.
Bipartite graph → maximum number of edges = ?
A. m×n
B. n(n−1)/2
C. n²
D. 2n
Answer: A
Solution:
Complete bipartite graph → edges = size of set1 × size of set2 = m×n.
41.
Directed graph → number of vertices = 5, number of edges = 7 → maximum possible edges = ?
A. 10
B. 20
C. 15
D. 25
Answer: B
Solution:
Directed graph → max edges = n(n−1) = 5×4 = 20.
42.
DFS tree → back edge indicates:
A. Cycle
B. Shortest path
C. Tree edge
D. Disconnected graph
Answer: A
Solution:
Back edge → from descendant to ancestor → indicates cycle.
43.
Graph with 6 vertices and 9 edges → connected → number of components = ?
A. 1
B. 2
C. 3
D. 4
Answer: A
Solution:
Connected graph → 1 component.
44.
In a weighted graph, negative weight cycles → shortest path?
A. Not defined
B. Defined
C. Always positive
D. Always zero
Answer: A
Solution:
Negative weight cycle → path can decrease indefinitely → shortest path undefined.
45.
Graph traversal → vertex visited once → guarantees:
A. BFS
B. DFS
C. Both
D. Neither
Answer: C
Solution:
Both BFS and DFS → each vertex visited once if marked.
46.
Adjacency list representation → efficient when:
A. Sparse graph
B. Dense graph
C. Complete graph
D. Cycle graph
Answer: A
Solution:
Sparse → fewer edges → adjacency list uses O(V+E) space efficiently.
47.
Adjacency matrix → efficient when:
A. Dense graph
B. Sparse graph
C. Tree
D. DAG
Answer: A
Solution:
Dense → many edges → adjacency matrix O(V²) acceptable.
48.
Topological sorting → multiple valid orders → graph property?
A. DAG
B. Graph with cycles
C. Complete graph
D. Undirected graph
Answer: A
Solution:
Topological sort → only DAGs → multiple valid orders if multiple sources exist.
49.
Number of edges in DAG with 6 vertices → max edges = ?
A. 15
B. 10
C. 20
D. 12
Answer: A
Solution:
DAG → max edges = n(n−1)/2 = 6×5/2 = 15.
50.
Eulerian cycle → exists in directed graph if:
A. In-degree = out-degree for all vertices
B. All vertices even degree
C. Only one odd-degree vertex
D. No edges
Answer: A
Solution:
Directed Eulerian cycle → each vertex in-degree = out-degree + graph connected.
51.
Bipartite graph → DFS coloring → two colors → detection of:
A. Odd-length cycle
B. Even-length cycle
C. Hamiltonian path
D. Eulerian cycle
Answer: A
Solution:
Odd-length cycle → violates 2-colorability → DFS detects.
52.
Number of edges in complete bipartite graph K5,7 = ?
A. 35
B. 12
C. 25
D. 30
Answer: A
Solution:
Edges = m×n = 5×7 = 35.
53.
Graph → adjacency matrix has 1s only in upper triangle → graph is:
A. Undirected
B. Directed
C. Weighted
D. Bipartite
Answer: B
Solution:
Upper triangle → edges from i → j only → directed graph.
54.
DFS → time complexity = ?
A. O(V+E)
B. O(V²)
C. O(E²)
D. O(log V)
Answer: A
Solution:
Visits all vertices and edges → O(V+E).
55.
BFS → time complexity = ?
A. O(V+E)
B. O(V²)
C. O(E²)
D. O(log V)
Answer: A
Solution:
Queue-based traversal → O(V+E).
56.
Graph → 7 vertices, 21 edges → must be:
A. Complete undirected
B. Tree
C. Cycle
D. DAG
Answer: A
Solution:
Undirected complete → n(n−1)/2 = 7×6/2 = 21.
57.
Number of edges in tree with 25 vertices = ?
A. 24
B. 25
C. 23
D. 26
Answer: A
Solution:
Tree → edges = vertices − 1 = 25 − 1 = 24.
58.
Prim’s algorithm → complexity using adjacency matrix = ?
A. O(V²)
B. O(E log V)
C. O(V+E)
D. O(V³)
Answer: A
Solution:
Adjacency matrix → select minimum weight edge at each step → O(V²).
59.
Kruskal’s algorithm → uses which data structure?
A. Disjoint set (Union-Find)
B. Stack
C. Queue
D. Priority queue
Answer: A
Solution:
Kruskal → Union-Find for cycle detection.
60.
DAG → longest path → time complexity using topological sort = ?
A. O(V+E)
B. O(V²)
C. O(E log V)
D. O(V³)
Answer: A
Solution:
Topological order → relax edges → O(V+E).
61.
Graph with negative edges but no negative cycles → shortest path → algorithm?
A. Bellman-Ford
B. Dijkstra
C. BFS
D. DFS
Answer: A
Solution:
Bellman-Ford → handles negative edges, detects cycles.
62.
Adjacency list → time to find all neighbors of a vertex = ?
A. O(degree of vertex)
B. O(V)
C. O(E)
D. O(1)
Answer: A
Solution:
Each neighbor stored in linked list → traverse all → O(degree).
63.
Graph → Eulerian path → directed → condition?
A. Exactly one vertex with out-degree − in-degree = 1, one with in-degree − out-degree = 1
B. All vertices even degree
C. No edges
D. Graph disconnected
Answer: A
Solution:
Directed Eulerian path → start vertex out-degree = in-degree+1, end vertex in-degree = out-degree+1.
64.
Graph → adjacency matrix → edge lookup complexity = ?
A. O(1)
B. O(V)
C. O(E)
D. O(log V)
Answer: A
Solution:
Matrix → direct access → O(1).
65.
Graph → adjacency list → edge lookup complexity = ?
A. O(degree of vertex)
B. O(1)
C. O(V²)
D. O(log V)
Answer: A
Solution:
Traverse linked list → O(degree).
66.
Cycle detection in directed graph → algorithm?
A. DFS + recursion stack
B. BFS
C. Dijkstra
D. Prim
Answer: A
Solution:
DFS → recursion stack → back edge → cycle detected.
67.
Number of edges in complete directed graph with n vertices = ?
A. n(n−1)
B. n(n−1)/2
C. n²
D. n
Answer: A
Solution:
Each vertex has n−1 outgoing edges → n(n−1).
68.
Number of edges in complete bipartite K3,5 = ?
A. 15
B. 8
C. 12
D. 7
Answer: A
Solution:
Edges = 3×5 = 15.
69.
Topological sort → number of valid orders depends on:
A. Number of sources
B. Number of vertices
C. Number of edges
D. Graph density
Answer: A
Solution:
Multiple sources → multiple valid topological orders.
70.
Bipartite graph → maximum edges = ?
A. m×n
B. n(n−1)/2
C. n²
D. 2n
Answer: A
Solution:
Edges = size of set1 × size of set2 = m×n.
71.
DFS → tree edge → indicates:
A. Edge leads to unvisited vertex
B. Back edge
C. Cross edge
D. Forward edge
Answer: A
Solution:
DFS tree edge → explores new vertex.
72.
DFS → back edge → indicates:
A. Cycle
B. Tree edge
C. Cross edge
D. Forward edge
Answer: A
Solution:
Back edge → descendant to ancestor → cycle.
73.
Number of edges in complete undirected graph with 12 vertices = ?
A. 66
B. 55
C. 72
D. 60
Answer: B
Solution:
Edges = n(n−1)/2 = 12×11/2 = 66 → double-check → yes 66.
74.
Number of edges in tree with 100 vertices = ?
A. 99
B. 100
C. 101
D. 98
Answer: A
Solution:
Tree → edges = vertices − 1 → 100 − 1 = 99.
75.
BFS → shortest path in weighted graph → only works if:
A. All edge weights equal
B. Negative edges exist
C. Any weights
D. Graph disconnected
Answer: A
Solution:
BFS → unweighted → shortest path in number of edges.
76.
DFS stack size worst-case = ?
A. O(V)
B. O(E)
C. O(log V)
D. O(1)
Answer: A
Solution:
DFS → recursive stack → max depth = O(V).
77.
DFS recursion → time complexity = ?
A. O(V+E)
B. O(V²)
C. O(E²)
D. O(log V)
Answer: A
Solution:
Each vertex and edge visited once → O(V+E).
78.
Graph → adjacency matrix → number of edges = 0 → type = ?
A. Null graph
B. Complete graph
C. Cycle
D. Tree
Answer: A
Solution:
No edges → null graph.
79.
Graph → strongly connected → property?
A. Every vertex reachable from every vertex
B. Only root reachable
C. DAG
D. Bipartite
Answer: A
Solution:
Strongly connected → all vertices mutually reachable.
80.
Number of edges in complete undirected graph with 20 vertices = ?
A. 190
B. 200
C. 210
D. 180
Answer: A
Solution:
Edges = n(n−1)/2 = 20×19/2 = 190.
81.
Eulerian cycle → undirected graph → condition:
A. Connected + all vertices even degree
B. Connected + two odd-degree vertices
C. Disconnected + all vertices even degree
D. None
Answer: A
Solution:
Eulerian cycle → all vertices even degree + connected.
82.
Hamiltonian cycle → definition:
A. Visits all vertices exactly once, returns to start
B. Visits all edges exactly once
C. Visits all vertices any number of times
D. DFS traversal
Answer: A
Solution:
Hamiltonian cycle → visit each vertex exactly once, return to start.
83.
DFS → cross edge → occurs in:
A. Directed graph
B. Undirected graph
C. Tree
D. Weighted graph
Answer: A
Solution:
Cross edge → between visited vertices in different branches → directed graphs.
84.
Number of edges in complete directed graph with 8 vertices = ?
A. 56
B. 28
C. 64
D. 49
Answer: A
Solution:
Edges = n(n−1) = 8×7 = 56.
85.
Adjacency matrix → symmetric → graph is:
A. Undirected
B. Directed
C. Weighted
D. Null
Answer: A
Solution:
Symmetry → undirected edges.
86.
Cycle detection in undirected graph → algorithm?
A. DFS + parent tracking
B. BFS
C. Dijkstra
D. Prim
Answer: A
Solution:
DFS → if visited vertex ≠ parent → cycle exists.
87.
Strongly connected components → algorithm?
A. Kosaraju
B. BFS
C. Dijkstra
D. Prim
Answer: A
Solution:
Kosaraju → identifies SCCs.
88.
Number of edges in DAG with 7 vertices, topologically sorted → max edges = ?
A. 21
B. 42
C. 14
D. 28
Answer: A
Solution:
DAG → max edges = n(n−1)/2 = 7×6/2 = 21.
89.
Graph → adjacency list → edge existence check → complexity = ?
A. O(degree of vertex)
B. O(1)
C. O(V)
D. O(E)
Answer: A
Solution:
Traverse list → O(degree).
90.
DFS → tree edge → indicates:
A. Leads to unvisited vertex
B. Leads to ancestor
C. Cross edge
D. Forward edge
Answer: A
Solution:
Tree edge → explores new vertex.
91.
DFS → forward edge → definition:
A. Ancestor → descendant
B. Back edge
C. Cross edge
D. Tree edge
Answer: A
Solution:
Forward edge → from ancestor to descendant (not tree edge).
92.
BFS → time to find shortest path in unweighted graph = ?
A. O(V+E)
B. O(V²)
C. O(E²)
D. O(log V)
Answer: A
Solution:
Queue-based → linear in vertices + edges.
93.
Graph → adjacency list → space complexity = ?
A. O(V+E)
B. O(V²)
C. O(E²)
D. O(1)
Answer: A
Solution:
List stores all vertices + edges.
94.
Graph → adjacency matrix → space complexity = ?
A.
O(V²)
B. O(V+E)
C. O(E)
D. O(V)
Answer: A
Solution:
Matrix → n×n entries.
95.
Graph → negative cycles exist → shortest path algorithm fails → which algorithm?
A. Dijkstra
B. BFS
C. DFS
D. Prim
Answer: A
Solution:
Dijkstra → cannot handle negative cycles.
96.
Graph → Hamiltonian path → definition:
A. Visits each vertex exactly once
B. Visits all edges exactly once
C. DFS traversal
D. BFS traversal
Answer: A
Solution:
Hamiltonian path → each vertex visited exactly once (no return).
97.
Graph → number of components = 1 → graph is:
A. Connected
B. Disconnected
C. Null
D. DAG
Answer: A
Solution:
1 component → connected graph.
98.
Number of edges in K4,5 → complete bipartite graph = ?
A. 20
B. 9
C. 15
D. 18
Answer: A
Solution:
Edges = m×n = 4×5 = 20.
99.
Bipartite graph → 2-colorable → property:
A. No odd cycles
B. Eulerian cycle
C. Hamiltonian cycle
D. Self-loops
Answer: A
Solution:
Bipartite → 2-colorable → no odd-length cycles.
100.
Graph → strongly connected → all vertices reachable → algorithm to check?
A. Kosaraju / Tarjan
B. BFS
C. Dijkstra
D. DFS alone
Answer: A
Solution:
SCC detection → Kosaraju/Tarjan → checks mutual reachability.