Q.1 Which of the following is a simple graph?
Graph with parallel edges
Graph with self-loops
Graph with neither loops nor multiple edges
Graph with directed edges
Explanation - A simple graph is defined as a graph without loops and without multiple edges.
Correct answer is: Graph with neither loops nor multiple edges
Q.2 What is the degree of a vertex in a graph?
Number of loops at the vertex
Number of edges incident to the vertex
Number of vertices adjacent to it
Sum of degrees of all vertices
Explanation - The degree of a vertex is defined as the number of edges incident to it.
Correct answer is: Number of edges incident to the vertex
Q.3 In a simple undirected graph with 5 vertices, what is the maximum number of edges?
10
15
20
25
Explanation - Maximum number of edges in a simple graph with n vertices is n(n-1)/2. For n=5, it is 5×4/2 = 10.
Correct answer is: 10
Q.4 Which graph traversal uses a queue data structure?
Depth First Search
Breadth First Search
Dijkstra’s Algorithm
Kruskal’s Algorithm
Explanation - BFS uses a queue to explore all neighbors of a vertex level by level.
Correct answer is: Breadth First Search
Q.5 Which of the following is NOT a property of a tree?
It is a connected graph
It contains no cycles
It always has even number of vertices
It has exactly n-1 edges for n vertices
Explanation - Trees can have any number of vertices, even or odd, as long as they satisfy connectedness and acyclicity.
Correct answer is: It always has even number of vertices
Q.6 What is the chromatic number of a complete graph with 4 vertices (K4)?
2
3
4
5
Explanation - A complete graph Kn requires n colors for proper coloring, so K4 requires 4 colors.
Correct answer is: 4
Q.7 Which algorithm is commonly used to find the shortest path in a weighted graph?
Kruskal’s Algorithm
Prim’s Algorithm
Dijkstra’s Algorithm
DFS
Explanation - Dijkstra’s algorithm is used to find the shortest path in a weighted graph with non-negative weights.
Correct answer is: Dijkstra’s Algorithm
Q.8 In a complete bipartite graph K3,3, how many edges are there?
6
9
12
15
Explanation - In a complete bipartite graph Km,n, the number of edges is m×n. So K3,3 has 3×3=9 edges.
Correct answer is: 9
Q.9 What is a planar graph?
Graph that can be colored with 2 colors
Graph that can be drawn without edges crossing
Graph with loops only
Graph with degree 2 at each vertex
Explanation - A planar graph can be drawn in a plane without edges crossing.
Correct answer is: Graph that can be drawn without edges crossing
Q.10 Which theorem states that the sum of degrees of all vertices in a graph is twice the number of edges?
Euler’s Theorem
Degree-Sum Formula
Handshaking Lemma
Kirchhoff’s Theorem
Explanation - The Handshaking Lemma states that Σdeg(v) = 2|E| for any undirected graph.
Correct answer is: Handshaking Lemma
Q.11 Which of the following is a Hamiltonian cycle?
A cycle that visits each edge once
A cycle that visits each vertex once
A cycle that repeats vertices
A cycle in a bipartite graph
Explanation - Hamiltonian cycle visits every vertex exactly once before returning to the start.
Correct answer is: A cycle that visits each vertex once
Q.12 Which of the following is Euler’s formula for a connected planar graph?
V - E + F = 1
V - E + F = 2
V + E + F = 0
V + E - F = 2
Explanation - Euler’s formula states V - E + F = 2 for connected planar graphs.
Correct answer is: V - E + F = 2
Q.13 Which traversal is best suited for finding connected components in a graph?
DFS
BFS
Both DFS and BFS
Dijkstra’s Algorithm
Explanation - Both DFS and BFS can be used to explore and find connected components in a graph.
Correct answer is: Both DFS and BFS
Q.14 In a directed acyclic graph (DAG), what is impossible?
Topological ordering
Cycle
Source vertex
Sink vertex
Explanation - By definition, a DAG cannot contain any cycle.
Correct answer is: Cycle
Q.15 Which data structure is most suitable for implementing Prim’s algorithm?
Queue
Stack
Priority Queue
Linked List
Explanation - Prim’s algorithm uses a priority queue to pick the minimum weight edge efficiently.
Correct answer is: Priority Queue
Q.16 Which of the following graphs has all vertices of degree 2?
Tree
Cycle
Path
Star
Explanation - In a cycle, every vertex has degree exactly 2.
Correct answer is: Cycle
Q.17 Which problem can be solved using topological sorting?
Cycle detection
Shortest path in unweighted graph
Job scheduling with dependencies
Minimum spanning tree
Explanation - Topological sorting is used in scheduling problems with precedence constraints.
Correct answer is: Job scheduling with dependencies
Q.18 What is the maximum number of edges in a bipartite graph with n vertices?
n(n-1)/2
n^2
n^2/4
2n
Explanation - The maximum occurs when vertices are equally divided, giving n/2 × n/2 = n^2/4 edges.
Correct answer is: n^2/4
Q.19 Which graph algorithm is used for finding articulation points?
DFS based algorithm
BFS based algorithm
Dijkstra’s Algorithm
Kruskal’s Algorithm
Explanation - Articulation points are usually found using DFS with discovery and low time values.
Correct answer is: DFS based algorithm
Q.20 What is the diameter of a graph?
The longest edge
The largest degree
The greatest distance between any two vertices
The number of connected components
Explanation - Graph diameter is the maximum eccentricity among all vertices.
Correct answer is: The greatest distance between any two vertices
Q.21 Which algorithm is used to detect cycles in a directed graph?
DFS
BFS
Dijkstra’s Algorithm
Prim’s Algorithm
Explanation - Cycle detection in directed graphs is commonly done using DFS with recursion stack tracking.
Correct answer is: DFS
Q.22 Which graph representation uses less space for sparse graphs?
Adjacency matrix
Adjacency list
Incidence matrix
Cross matrix
Explanation - Adjacency list is more space-efficient for sparse graphs.
Correct answer is: Adjacency list
Q.23 Which graph has an Eulerian circuit?
A graph where all vertices have even degree
A graph with all vertices having odd degree
A tree
Any bipartite graph
Explanation - Eulerian circuits exist in graphs where every vertex has an even degree and the graph is connected.
Correct answer is: A graph where all vertices have even degree
Q.24 Which traversal is used in solving maze problems?
DFS
BFS
Both DFS and BFS
None
Explanation - Both DFS and BFS can be used depending on whether you need the shortest path (BFS) or just any path (DFS).
Correct answer is: Both DFS and BFS
Q.25 Which of the following is NOT a type of graph?
Null graph
Complete graph
Regular graph
Circular graph
Explanation - Circular graph is not a standard type; common types are null, complete, bipartite, and regular.
Correct answer is: Circular graph