# Bipartite Graphs in Data Structure and Algorithms MCQs

Q1. There are four students in a class namely A, B, C and D. A tells that a triangle is a bipartite graph. B tells pentagon is a bipartite graph. C tells square is a bipartite graph. D tells heptagon is a bipartite graph. Who among the following is correct?.

A.  "A".

B.  "B".

C.  "C".

D.  "D".

Q2. A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?.

A.  n.

B.  n/2.

C.  n/4.

D.  data insufficient.

Q3. When is a graph said to be bipartite?.

A.  If it can be divided into two independent sets A and B such that each edge connects a vertex from to A to B.

B.  If the graph is connected and it has odd number of vertices.

C.  If the graph is disconnected.

D.  If the graph has at least n/2 vertices whose degree is greater than n/2.

Answer=  If it can be divided into two independent sets A and B such that each edge connects a vertex from to A to B

Q4. Are trees bipartite?.

A.  Yes.

B.  No.

C.  Yes if it has even number of vertices.

D.  No if it has odd number of vertices.

Q5. A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite).

A. 100.

B. 140.

C. 80.

D. 20.

Q6. Given that a graph contains no odd cycle. Is it enough to tell that it is bipartite?.

A.  Yes.

B.  No.

C. Nothing Can be Said.

D. None of the mentioned.

Q7. Can there exist a graph which is both eulerian and is bipartite?.

A.  Yes.

B.  No.

C.  Yes if it has even number of edges.

D.  Nothing can be said.

Q8. A graph is found to be 2 colorable. What can be said about that graph?.

A.  The given graph is eulerian.

B.  The given graph is bipartite.

C.  The given graph is hamiltonian.

D.  The given graph is planar.

Answer=  The given graph is bipartite

Q9. Which type of graph has no odd cycle in it?.

A.  Bipartite.

B.  Histogram.

C.  Cartesian.

D.  Pie.

Q10. What type of graph has chromatic number less than or equal to 2?.

A.  Histogram.

B.  Bipartite.

C.  Cartesian.

D.  Tree.

Q11. Which of the following is the correct type of spectrum of the bipartite graph?.

A.  Symmetric.

B.  Anti – Symmetric.

C.  Circular.

D.  Exponential.

Q12. Which of the following is the property of the bipartite graph?.

A.  No Odd Cycle.

B.  Symmetric spectrum.

C.  Chromatic Number Is Less Than or Equal to 2.

D.  All of the mentioned.

Q13. Which one of the following is the chromatic number of bipartite graph?.

A. 1.

B. 4.

C. 3.

D. 5.

Q14. Which graph has a size of minimum vertex cover equal to maximum matching?.

A.  Cartesian.

B.  Tree.

C.  Heap.

D.  Bipartite.

Q15. Which theorem gives the relation between the minimum vertex cover and maximum matching?.

A.  Konig’s Theorem.

B.  Kirchhoff’s Theorem.

C.  Kuratowski’s Theorem.

D.  Kelmans Theorem.

Q16. Which of the following is the perfect graph?.

A.  Compliment of Line Graph of Bipartite Graph.

B.  Compliment of Bipartite Graph.

C.  Line Graph of Bipartite Graph.

D.  All of the mentioned.

Q17. Which graph has chromatic number 2?.

A.  Compliment of Line Graph of Bipartite Graph.

B.  Compliment of Bipartite Graph.

C.  Line Graph of Bipartite Graph.

D.  All of the mentioned.

Q18. Which of the following has maximum clique size 2?.

A.  Perfect graph.

B.  Tree.

C.  Histogram.

D.  Cartesian.

Q19. What is the chromatic number of compliment of line graph of bipartite graph?.

A. 0.

B. 1.

C. 2.

D. 3.

Q20. What is the clique size of the line graph of bipartite graph?.

A. 0.

B. 1.

C. 2.

D. 3.

Q21. Is it possible to have a negative chromatic number of bipartite graph?.

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q22. Is it true that the perfect graph has forbidden graph characterization?.

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q23. Which structure can be modelled by using Bipartite graph?.

A.  Hypergraph.

B.  Perfect Graph.

C.  Hetero Graph.

D.  Directed Graph.

Q24. 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.

Q25. Which graph is also known as biclique?.

A.  Histogram.

B.  Complete Bipartite.

C.  Cartesian.

D.  Tree.

Q26. Which term defines all the complete bipartite graph that are trees?.

A.  Symmetric.

B.  Anti – Symmetric.

C.  Circular.

D.  Stars.

Q27. How many edges does a n vertex triangle free graph contains?.

A.  n^2.

B.  n^2 + 2.

C.  n^2 / 4.

D.  n3.

Q28. Which graph is used to define the claw free graph?.

A.  Bipartite Graph.

B.  Claw Graph.

C.  Star Graph.

D.  Cartesian Graph.

Q29. 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.

Q30. 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.

Q31. What are the Eigen values for the adjacency matrix of the complete bipartite graph?.

A.  (nm)1/2.

B.  (-nm)1/2.

C. 0.

D.  All of the mentioned.

Q32. Which complete graph is not present in minor of Outer Planar Graph?.

A.  K3, 3.

B.  K3, 1.

C.  K3, 2.

D.  K1, 1.

Q33. Is every complete bipartite graph a Moore Graph..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q34. 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.

Answer=  n + m – 2

Q35. What are the Eigen values for the Laplacian matrix of the complete bipartite graph?.

A.  n + m.

B.  n.

C. 0.

D.  All of the mentioned.

Q36. 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.

Q37. Recursion is a method in which the solution of a problem depends on ____________.

A.  Larger instances of different problems.

B.  Larger instances of the same problem.

C.  Smaller instances of the same problem.

D.  Smaller instances of different problems.

Answer=  Smaller instances of the same problem

Q38. Which of the following problems can be solved using recursion?.

A.  Factorial of a number.

B.  Nth fibonacci number.

C.  Length of a string.

D.  All of the mentioned.