Engineering Questions with Answers - Multiple Choice Questions

# Data Structure MCQ – Undirected Graph

1 - Question

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: There can be at most, n*n edges in an undirected graph.

2 - Question

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: Euler’s Identity says V – E + R = 1+ number of connected components.

3 - Question

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 start and end vertices for the path are same the answer would be 0 otherwise 2.

4 - Question

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.

5 - Question

All paths and cyclic graphs are bipartite graphs.
a) True
b) False

Explanation: Only paths and even cycles are bipartite graphs.

6 - Question

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: Only the first and the last vertex would have degree 1, others would be of degree 2.

7 - Question

All trees with n vertices consists of n-1 edges.
a) True
b) False

Explanation: A trees is acyclic in nature.

8 - Question

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 are Complete graphs with 4 vertices.

9 - Question

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 resultant graph would be a Bipartite Graph having {A,C,E} and {D, B} as its subgroups.

10 - Question

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)