Complete Bipartite Graph Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Complete Bipartite Graph”.

1. Which type of graph has all the vertex of the first set connected to all the vertex of the second set?
a) Bipartite
b) Complete Bipartite
c) Cartesian
d) Pie
View Answer

Answer: b
Explanation: The graph is known as Bipartite if the graph does not contain any odd length cycle in it. The complete bipartite graph has all the vertex of first set connected to all the vertex of second set.

2. Which graph is also known as biclique?
a) Histogram
b) Complete Bipartite
c) Cartesian
d) Tree
View Answer

Answer: b
Explanation: A graph is known as complete bipartite graph if and only if it has all the vertex of first set connected to all the vertex of second set. Complete Bipartite graph is also known as Biclique.

3. Which term defines all the complete bipartite graph that are trees?
a) Symmetric
b) Anti – Symmetric
c) Circular
d) Stars
View Answer

Answer: d
Explanation: Star is a complete bipartite graph with one internal node and k leaves. Therefore, all complete bipartite graph which is trees are known as stars in graph theory.
advertisement
advertisement

4. How many edges does a n vertex triangle free graph contains?
a) n2
b) n2 + 2
c) n2 / 4
d) n3
View Answer

Answer: c
Explanation: A n vertex triangle free graph contains a total of n2 / 4 number of edges. This is stated by Mantel’s Theorem which is a special case in Turan’s theorem for r=2.

5. Which graph is used to define the claw free graph?
a) Bipartite Graph
b) Claw Graph
c) Star Graph
d) Cartesian Graph
View Answer

Answer: b
Explanation: Star is a complete bipartite graph with one internal node and k leaves. Star with three edges is called a claw. Hence this graph is used to define claw free graph.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. What is testing of a complete bipartite subgraph in a bipartite graph problem called?
a) P Problem
b) P-Complete Problem
c) NP Problem
d) NP-Complete Problem
View Answer

Answer: d
Explanation: NP stands for nondeterministic polynomial time. In a bipartite graph, the testing of a complete bipartite subgraph in a bipartite graph is an NP-Complete Problem.

7. Which graph cannot contain K3, 3 as a minor of graph?
a) Planar Graph
b) Outer Planar Graph
c) Non Planar Graph
d) Inner Planar Graph
View Answer

Answer: a
Explanation: Minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off vertices from a graph. Hence Planar graph cannot contain K3, 3 as a minor graph.
advertisement

8. Which of the following is not an Eigen value of the adjacency matrix of the complete bipartite graph?
a) (nm)1/2
b) (-nm)1/2
c) 0
d) nm
View Answer

Answer: d
Explanation: The adjacency matrix is a square matrix that is used to represent a finite graph. Therefore, the Eigen values for the complete bipartite graph is found to be (nm)1/2, (-nm)1/2, 0.

9. Which complete graph is not present in minor of Outer Planar Graph?
a) K3, 3
b) K3, 1
c) K3, 2
d) K1, 1
View Answer

Answer: c
Explanation: Minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off vertices from a graph. Hence Outer Planar graph cannot contain K3, 2 as a minor graph.
advertisement

10. Is every complete bipartite graph a Moore Graph.
a) True
b) False
View Answer

Answer: a
Explanation: In graph theory, Moore graph is defined as a regular graph that has a degree d and diameter k. therefore, every complete bipartite graph is a Moore Graph.

11. What is the multiplicity for the adjacency matrix of complete bipartite graph for 0 Eigen value?
a) 1
b) n + m – 2
c) 0
d) 2
View Answer

Answer: b
Explanation: The adjacency matrix is a square matrix that is used to represent a finite graph. The multiplicity of the adjacency matrix off complete bipartite graph with Eigen Value 0 is n + m – 2.

12. Which of the following is not an Eigen value of the Laplacian matrix of the complete bipartite graph?
a) n + m
b) n
c) 0
d) n*m
View Answer

Answer: d
Explanation: The laplacian matrix is used to represent a finite graph in the mathematical field of Graph Theory. Therefore, the Eigen values for the complete bipartite graph is found to be n + m, n, m, 0.

13. What is the multiplicity for the laplacian matrix of the complete bipartite graph for n Eigen value?
a) 1
b) m-1
c) n-1
d) 0
View Answer

Answer: b
Explanation: The laplacian matrix is used to represent a finite graph in the mathematical field of Graph Theory. The multiplicity of the laplacian matrix of complete bipartite graph with Eigen Value n is m-1.

14. Is it true that every complete bipartite graph is a modular graph.
a) True
b) False
View Answer

Answer: a
Explanation: Yes, the modular graph in graph theory is defined as an undirected graph in which all three vertices have at least one median vertex. So all complete bipartite graph is called modular graph.

15. How many spanning trees does a complete bipartite graph contain?
a) nm
b) mn-1 * nn-1
c) 1
d) 0
View Answer

Answer: b
Explanation: Spanning tree of a given graph is defined as the subgraph or the tree with all the given vertices but having minimum number of edges. So, there are a total of mn-1 * nn-1 spanning trees for a complete bipartite graph.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

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

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.