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".
Answer= "C"
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.
Answer= n/2
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.
Answer= Yes
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.
Answer= 100
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.
Answer= Yes
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.
Answer= Yes
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.
Answer= Bipartite
Q10. What type of graph has chromatic number less than or equal to 2?.
A. Histogram.
B. Bipartite.
C. Cartesian.
D. Tree.
Answer= Bipartite
Q11. Which of the following is the correct type of spectrum of the bipartite graph?.
A. Symmetric.
B. Anti – Symmetric.
C. Circular.
D. Exponential.
Answer= Symmetric
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.
Answer= 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.
Answer= 1
Q14. Which graph has a size of minimum vertex cover equal to maximum matching?.
A. Cartesian.
B. Tree.
C. Heap.
D. Bipartite.
Answer= 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.
Answer= Kuratowski’s 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.
Answer= 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.
Answer= All of the mentioned
Q18. Which of the following has maximum clique size 2?.
A. Perfect graph.
B. Tree.
C. Histogram.
D. Cartesian.
Answer= Perfect graph
Q19. What is the chromatic number of compliment of line graph of bipartite graph?.
A. 0.
B. 1.
C. 2.
D. 3.
Answer= 2
Q20. What is the clique size of the line graph of bipartite graph?.
A. 0.
B. 1.
C. 2.
D. 3.
Answer= 2
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.
Answer= FALSE
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.
Answer= TRUE
Q23. Which structure can be modelled by using Bipartite graph?.
A. Hypergraph.
B. Perfect Graph.
C. Hetero Graph.
D. Directed Graph.
Answer= Hypergraph
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.
Answer= Complete Bipartite
Q25. Which graph is also known as biclique?.
A. Histogram.
B. Complete Bipartite.
C. Cartesian.
D. Tree.
Answer= Complete Bipartite
Q26. Which term defines all the complete bipartite graph that are trees?.
A. Symmetric.
B. Anti – Symmetric.
C. Circular.
D. Stars.
Answer= 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.
Answer= n^2 / 4
Q28. Which graph is used to define the claw free graph?.
A. Bipartite Graph.
B. Claw Graph.
C. Star Graph.
D. Cartesian Graph.
Answer= Claw 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.
Answer= 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.
Answer= 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.
Answer= 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.
Answer= K3, 2
Q33. Is every complete bipartite graph a Moore Graph..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= TRUE
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.
Answer= 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.
Answer= m-1
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.
Answer= All of the mentioned