This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Properties of Bipartite Graphs”.
1. Which type of graph has no odd cycle in it?
a) Bipartite
b) Histogram
c) Cartesian
d) Pie
View Answer
Explanation: The graph is known as Bipartite if the graph does not contain any odd length cycle in it. Odd length cycle means a cycle with the odd number of vertices in it.
2. What type of graph has chromatic number less than or equal to 2?
a) Histogram
b) Bipartite
c) Cartesian
d) Tree
View Answer
Explanation: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is chromatic number.
3. Which of the following is the correct type of spectrum of the bipartite graph?
a) Symmetric
b) Anti – Symmetric
c) Circular
d) Exponential
View Answer
Explanation: The spectrum of the bipartite graph is symmetric in nature. The spectrum is the property of graph that are related to polynomial, Eigen values, Eigen vectors of the matrix related to graph.
4. Which of the following is not a property of the bipartite graph?
a) No Odd Cycle
b) Symmetric spectrum
c) Chromatic Number Is Less Than or Equal to 2
d) Asymmetric spectrum
View Answer
Explanation: A graph is known to be bipartite if it has odd length cycle number. It also has symmetric spectrum and the bipartite graph contains the total chromatic number less than or equal to 2.
5. Which one of the following is the chromatic number of bipartite graph?
a) 1
b) 4
c) 3
d) 5
View Answer
Explanation: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is the chromatic number.
6. Which graph has a size of minimum vertex cover equal to maximum matching?
a) Cartesian
b) Tree
c) Heap
d) Bipartite
View Answer
Explanation: The Konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. Bipartite graph has a size of minimum vertex cover equal to maximum matching.
7. 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
View Answer
Explanation: The Konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. Bipartite graph has a size of minimum vertex cover equal to maximum matching.
8. Which of the following is not a property of perfect graph?
a) Compliment of Line Graph of Bipartite Graph
b) Compliment of Bipartite Graph
c) Line Graph of Bipartite Graph
d) Line Graph
View Answer
Explanation: TThe Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is known as a perfect graph in graph theory. Normal line graph is not a perfect graph whereas line perfect graph is a graph whose line graph is a perfect graph.
9. Which of the following graphs don’t have chromatin number less than or equal to 2?
a) Compliment of Line Graph of Bipartite Graph
b) Compliment of Bipartite Graph
c) Line Graph of Bipartite Graph
d) Wheel graph
View Answer
Explanation: The perfect bipartite graph has chromatic number 2. Also, the Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is known as perfect graph in graph theory. Wheel graph Wn has chromatin number 3 if n is odd and 4 if n is even.
10. Which of the following has maximum clique size 2?
a) Perfect graph
b) Tree
c) Histogram
d) Cartesian
View Answer
Explanation: The perfect bipartite graph has clique size 2. Also, the clique size of Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is 2.
11. What is the chromatic number of compliment of line graph of bipartite graph?
a) 0
b) 1
c) 2
d) 3
View Answer
Explanation: The perfect bipartite graph has chromatic number 2. So the Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph has chromatic number 2.
12. What is the clique size of the line graph of bipartite graph?
a) 0
b) 1
c) 2
d) 3
View Answer
Explanation: The perfect bipartite graph has clique size 2. So the clique size of Compliment of Line Graph of Bipartite Graph, Compliment of Bipartite Graph, Line Graph of Bipartite Graph and every Bipartite Graph is 2.
13. It is possible to have a negative chromatic number of bipartite graph.
a) True
b) False
View Answer
Explanation: A graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. The smallest number of graphs needed to color the graph is the chromatic number. But the chromatic number cannot be negative.
14. Every Perfect graph has forbidden graph characterization.
a) True
b) False
View Answer
Explanation: Berge theorem proves the forbidden graph characterization of every perfect graphs. Because of that reason every bipartite graph is perfect graph.
15. Which structure can be modelled by using Bipartite graph?
a) Hypergraph
b) Perfect Graph
c) Hetero Graph
d) Directed Graph
View Answer
Explanation: A combinatorial structure such as Hypergraph can be made using the bipartite graphs. A hypergraph in graph theory is a type of graph in which edge can join any number of vertices.
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.
- Practice Computer Science MCQs
- Check Computer Science Books
- Practice Data Structure MCQ
- Check Design and Analysis of Algorithms Books
- Check Programming Books
