Data Structure Questions and Answers – Undirected Graph

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

1. 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)
View Answer

Answer: d
Explanation: There can be at most, n*n edges in an undirected graph.

2. 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
View Answer

Answer: b
Explanation: Euler’s Identity says V – E + R = 1+ number of connected components.

3. 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
View Answer

Answer: d
Explanation: If the start and end vertices for the path are same the answer would be 0 otherwise 2.
advertisement
advertisement

4. 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
View Answer

Answer: b
Explanation: Statements iii) and v) are correct.

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

Answer: b
Explanation: Only paths and even cycles are bipartite graphs.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. 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
View Answer

Answer: a
Explanation: Only the first and the last vertex would have degree 1, others would be of degree 2.

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

Answer: a
Explanation: A trees is acyclic in nature.
advertisement

8. Which of the following graphs are isomorphic to each other?
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
View Answer

Answer: d
Explanation: All three graphs are Complete graphs with 4 vertices.

9. In the given graph which edge should be removed to make it a Bipartite Graph?
A-C edge should be removed to make it Bipartite Graph having {A,C,E} & {D, B}
a) A-C
b) B-E
c) C-D
d) D-E
View Answer

Answer: a
Explanation: The resultant graph would be a Bipartite Graph having {A,C,E} and {D, B} as its subgroups.
advertisement

10. 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)
View Answer

Answer: b
Explanation: A graph can be checked for being Bipartite by seeing if it is 2-colorable or not, which can be obtained with the help of BFS.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.