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

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 D

A Simple Graph is a type of graph that does not contain any parallel edges (multiple edges) or self-loops (an edge from a vertex to itself). Each edge in a simple graph connects two distinct vertices, and there can be at most one edge between any pair of vertices.

Option B

A Minimum Spanning Tree (MST) is a tree formed from a connected weighted graph such that:

• All vertices are connected.
• No cycle is formed.
• The total sum of edge weights is minimum.

In a graph having n vertices, the Minimum Spanning Tree always contains (n-1) edges.
The given graph contains the following weighted edges:

To construct the Minimum Spanning Tree, we select edges with the smallest weights while avoiding cycles.
Step 1:

• Select edge Q – R having minimum weight 5.

Step 2:

• Select edge S – T having weight 10.

Step 3:

• Select edge Q – T having weight 15.

Now vertices Q, R, S, T become connected without forming a cycle.
Step 4:

• Vertex P is still disconnected. The minimum edge connected to P is P – Q having weight 30.

Now all vertices are connected and the spanning tree is complete.

Selected Edges:

Total Weight of MST : 5+10+15+30 = 60
Thus, the total weight of the Minimum Spanning Tree is 60.

Option C

In an adjacency matrix, we represent a graph using a two-dimensional array of size n×n, where n is the number of vertices. Each row and column correspond to a vertex, and the value stored in a cell tells us whether an edge exists between two vertices.

If the graph is weighted, the cell stores the weight instead of just 0 or 1. Since the matrix always needs space for n² entries, the space complexity is O(n²). This representation can be used for directed or undirected graphs as well as weighted or unweighted graphs.

The only drawback is that it uses more memory for sparse graphs, but it provides quick access to check if an edge exists between two vertices.

Option B

Breadth First Search (BFS) explores a graph level by level, meaning it visits all the neighboring vertices of a node before moving to the next level. To achieve this order, BFS uses a Queue, which follows the First In First Out (FIFO) principle. 
Depth First Search (DFS), on the other hand, explores a graph by going as deep as possible along one path before backtracking. This behavior is naturally supported by a Stack, which follows the Last In First Out (LIFO) principle.

Option C

Depth First Search (DFS) is a graph traversal algorithm that visits all vertices and edges of a graph.
The time complexity of DFS depends on how the graph is represented:
Adjacency Matrix:
In an adjacency matrix, we use an n×n matrix to represent edges. For each vertex, we must check all n possible vertices to see if an edge exists.
For n vertices, we check n entries for each vertex, so the total time complexity becomes O(n²).
Adjacency List:
In an adjacency list, each vertex stores only its connected neighbors, so during DFS each vertex is visited once taking O(n) time and each edge is traversed once taking O(e) time, resulting in a total time complexity of O(n+e).

• Both DFS and BFS have the same time complexity, it only depends on the graph representation.

Option B

Dijkstra’s Algorithm is a greedy algorithm used in graph theory to find the shortest path from a source node to all other nodes in a graph with non-negative edge weights. It works by repeatedly selecting the node with the minimum distance and updating the distances of its neighboring nodes.

Option C

In an undirected graph, each edge connects two vertices and contributes 1 degree to each of its end vertices. Therefore, every edge adds a total of 2 to the sum of degrees of all vertices. 
If the graph has e edges, the total sum of the degrees of all n vertices becomes 2e. This result is known as the Handshaking Theorem in graph theory.