Graphs Data Structure : MCQs & PYQs with Explanation

Option B

The chromatic number of a graph is the minimum number of colors required to color the vertices so that no two adjacent vertices have the same color.
In the given graph, vertices such as e, f, g, and h form a structure where each is connected in a way that three colors are not sufficient to avoid conflicts between adjacent vertices. When we attempt coloring with 3 colors, at least two adjacent vertices will end up with the same color.
However, using 4 colors, we can assign colors to all vertices so that no adjacent vertices share the same color. Therefore, the minimum number of colors required is 4.

Option A

Different Shortest-Path Algorithms are designed for different types of path problems in graphs. The key is to identify how many sources and destinations are involved and what type of path computation is required.
(P)  A person wants to visit from one place to another place in the shortest period.

• This represents a situation where we want to find the shortest path from a starting point to a destination through stages.
• This is modeled using a Multi-stage Graph.

A Multi-Stage Graph Algorithm divides the graph into stages and computes the shortest path from the source to the destination using dynamic programming. It is commonly used when the movement must follow a stage-wise structure.
(Q)  A person wants to visit M places in shortest period.

• Here, a single person starts from one source and we want the shortest paths to multiple destinations.
• This is exactly the problem solved by Dijkstra’s Algorithm.

Dijkstra’s Algorithm computes the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edges.
(R)  All N persons want to visit all M places in shortest.

• This implies we need the shortest distance between every pair of locations.
• This type of problem is solved by Floyd’s Algorithm (Floyd–Warshall Algorithm).

Floyd’s Algorithm computes the shortest paths between every pair of vertices in a graph using dynamic programming and an adjacency matrix.

IMPORTANT ALGORITHMS:

Option B

In an undirected graph with n nodes and no self‑loops, the maximum number of edges occurs when every pair of distinct nodes is connected by exactly one edge. That is, the graph is a Complete Graph K_n.

• Each node can connect to n-1 other nodes.
• The total number of unordered pairs of nodes is [n(n−1)]/2. Which is the maximum number of edges in the graph.

Option B

We use the Handshaking Theorem, which states that the sum of the degrees of all vertices in an undirected graph equals twice the number of edges:
Sum of degrees of all vertices=2×Number of edges
Here, E=31. So,
Sum of degrees = Sum of degrees=2×31=62
The given condition is that each vertex has degree at least 3. Now, let the number of vertices be n. Then, Sum of degrees ≥ 3n. We already know the exact sum is 62, so, 3n ≤ 62.
Finally solve for n, n ≤ 62/3 = 20.66. Since the number of vertices must be an integer, the maximum possible number of vertices is 20.

Option A

A tree is a special type of graph that is connected and acyclic. This means all nodes are reachable from each other, and there is exactly one unique path between any two nodes.

• A tree with n nodes has exactly (n-1) edges.

Option D

A Spanning Tree of a graph is a subgraph that includes all the vertices of the graph and is connected without forming any cycles. For any connected graph with V vertices, a tree structure must have exactly V-1 edges to remain connected and acyclic.

Option C

Breadth First Search (BFS) is a graph traversal technique where we start from a chosen root vertex r and explore all the neighboring vertices first. It uses a Queue to keep track of which vertices to visit next.
What does d(r,u) mean?
Here d(r,u) represents the shortest distance from the root vertex r to vertex u, measured in terms of the number of edges on the shortest path connecting them. In an unweighted graph, this shortest distance is exactly the same as the level at which vertex u sits during the breadth first traversal.
The fundamental property of BFS is that it visits all vertices at distance 0 first, which is just the root itself, then all vertices at distance 1, then all vertices at distance 2, and so on, expanding outward layer by layer using the queue structure.
The question tells us that vertex u is visited before vertex v during the breadth first traversal. Since BFS always processes vertices in non-decreasing (increasing) order of their distance from the root, this means the distance of u from the root cannot be greater than the distance of v from the root.
This gives us d(r,u) ≤ d(r,v).
It is important to notice that this relationship uses less than or equal to, not strictly less than. This is because multiple vertices can exist at the exact same distance level from the root.
E.g.:
Consider the following given Graph-1.

As we know, BFS explores an undirected graph level by level. The important property is that vertices are visited in non-decreasing order of their shortest distance from the starting vertex r.
Graph 1: Vertices u and v are at the same distance, so, starting from r:

• r is at distance 0.
• p and q are at distance 1.
• u and v are at distance 2.

So, d(r,u)=2 and d(r,v)=2. BFS may visit u before v, or v before u, depending on the order in which adjacent vertices are processed. If u is visited before v, we have d(r,u)=d(r,v)=2. Therefore, d(r,u)≤d(r,v), means, strict inequality d(r,u)<d(r,v) is not necessary.
E.g.:
Consider the following given Graph-2.

Graph 2: Vertices u and v are not at the same distance, so, starting from r:

• r is at distance 0.
• p,q is at distance 1.
• u,z is at distance 2.
• v,w is at distance 3.

Therefore, d(r,u)=2 while d(r,v)=3. BFS will visit the level containing u before reaching the level containing v. Thus, d(r,u)<d(r,v).
So, if u is visited before v, the only guaranteed relationship is d(r,u)≤d(r,v). We cannot guarantee d(r,u)<d(r,v) because u and v can be at the same BFS level.
In short, BFS always visits vertices in increasing order of their shortest distance from the source. So, if u is visited before v, the distance of u can be less than or equal to the distance of v.

Option B

In graph theory, a graph is made up of a set of nodes, which are technically called vertices, and a set of line segments that connect pairs of these nodes, which are called edges.
Vertices represent the objects or points in the graph, while edges represent the connections or relationships between them.

Option A

Depth First Search (DFS), is a graph traversal technique where we start from a chosen vertex and travel as deep as possible along one path before backtracking and exploring other paths. It uses either a stack or recursion to keep track of which vertices still need to be explored.
The time complexity of Depth First Search (DFS) depends on how the graph is represented. For an adjacency list, DFS performs the following:

• Each vertex is visited at most once : O(V)
• The adjacency list of each vertex is examined, and overall every edge is examined at most once in a directed graph (and twice in an undirected graph) : O(E)

Therefore, the total time complexity is O(V+E)

Option A

Breadth First Search (BFS) is a graph traversal technique where we start from a chosen root vertex r and explore all the neighboring vertices first. It uses a Queue to keep track of which vertices to visit next.
What does d(r,u) mean?
Here d(r,u) represents the shortest distance from the root vertex r to vertex u, measured in terms of the number of edges on the shortest path connecting them. In an unweighted graph, this shortest distance is exactly the same as the level at which vertex u sits during the breadth first traversal.
The fundamental property of BFS is that it visits all vertices at distance 0 first, which is just the root itself, then all vertices at distance 1, then all vertices at distance 2, and so on, expanding outward layer by layer using the queue structure.
The question tells us that vertex u is visited before vertex v during the breadth first traversal. Since BFS always processes vertices in non-decreasing (increasing) order of their distance from the root, this means the distance of u from the root cannot be greater than the distance of v from the root.
This gives us d(r,u) ≤ d(r,v).
It is important to notice that this relationship uses less than or equal to, not strictly less than. This is because multiple vertices can exist at the exact same distance level from the root.
E.g.:
Consider the following given Graph-1.

As we know, BFS explores an undirected graph level by level. The important property is that vertices are visited in non-decreasing order of their shortest distance from the starting vertex r.
Graph 1: Vertices u and v are at the same distance, so, starting from r:

• r is at distance 0.
• p and q are at distance 1.
• u and v are at distance 2.

So, d(r,u)=2 and d(r,v)=2. BFS may visit u before v, or v before u, depending on the order in which adjacent vertices are processed. If u is visited before v, we have d(r,u)=d(r,v)=2. Therefore, d(r,u)≤d(r,v), means, strict inequality d(r,u)<d(r,v) is not necessary.
E.g.:
Consider the following given Graph-2.

Graph 2: Vertices u and v are not at the same distance, so, starting from r:

• r is at distance 0.
• p,q is at distance 1.
• u,z is at distance 2.
• v,w is at distance 3.

Therefore, d(r,u)=2 while d(r,v)=3. BFS will visit the level containing u before reaching the level containing v. Thus, d(r,u)<d(r,v).
So, if u is visited before v, the only guaranteed relationship is d(r,u)≤d(r,v). We cannot guarantee d(r,u)<d(r,v) because u and v can be at the same BFS level.
In short, BFS always visits vertices in increasing order of their shortest distance from the source. So, if u is visited before v, the distance of u can be less than or equal to the distance of v.