Data Structure Questions and Answers – Undirected Graph


This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Undirected Graph”.

1. What would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix?
A) O(E*E)
B) O(V*V)
C) O(E)
D) O(V)

Explanation: A graph’s bipartiteness can be determined by determining whether it is 2-colorable or not, which can be done with the aid of BFS.

2. What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.
A) n-2
B) n
C) 2
D) 0

Explanation: Just the first and last vertex would have a degree of one, while the rest would have a degree of two.

3. All trees with n vertices consists of n-1 edges.
A) True
B) False

Explanation: A tree’s life cycle is acyclic.

4. The number of possible undirected graphs which may have self loops but no multiple edges and have n vertices is ________
A) 2((n*(n-1))/2)
B) 2((n*(n+1))/2)
C) 2((n-1)*(n-1))/2)
D) 2((n*n)/2)

Explanation: In an undirected graph, there can only be n*n edges.

5. Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions. What will be the number of connected components?
A) 1
B) 2
C) 3
D) 4

Explanation: V – E + R = 1+ number of connected components, according to Euler’s Identity.

6. Number of vertices with odd degrees in a graph having a eulerian walk is ________
A) 0
B) Can’t be predicted
C) 2
D) either 0 or 2

Explanation: If the path’s start and end vertices are the same, the answer is 0, otherwise 2.

7. How many of the following statements are correct?
i) All cyclic graphs are complete graphs.
ii) All complete graphs are cyclic graphs.
iii) All paths are bipartite.
iv) All cyclic graphs are bipartite.
v) There are cyclic graphs which are complete.
A) 1
B) 2
C) 3
D) 4

Explanation: Statements iii) and v) are correct.

8. All paths and cyclic graphs are bipartite graphs.
A) True
B) False

Explanation: Bipartite graphs are just paths and also cycles.

9. Which of the following graphs are isomorphic to each other?


A) fig 1 and fig 2
B) fig 2 and fig 3
C) fig 1 and fig 3
D) fig 1, fig 2 and fig 3

Explanation: All three graphs have four vertices and are complete graphs.

9. In the given graph which edge should be removed to make it a Bipartite Graph?


A) A-C
B) B-E
C) C-D
D) D-E

Explanation: The resulting graph will be a Bipartite Graph with subgroups A,C,E, and D, B.

An undirected graph is a set of points (known as vertices or nodes) that are bound by edges that are all bidirectional. An undirected network is another name for an undirected graph. A guided graph, on the other hand, is one in which the edges all point in the same direction. Edges in undirected graphs do not have a path. Every edge can be traversed in both directions, indicating a two-way relationship. Directed graphs have edges that have a specific path. Each edge can only be traversed in one direction, indicating that the relationship is one-way.

Leave a Reply

Your email address will not be published. Required fields are marked *