Properties of Bipartite Graphs Multiple Choice Questions and Answers (MCQs)

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

Answer: a
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

Answer: b
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

Answer: a
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.
advertisement
advertisement

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

Answer: d
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

Answer: a
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.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. Which graph has a size of minimum vertex cover equal to maximum matching?
a) Cartesian
b) Tree
c) Heap
d) Bipartite
View Answer

Answer: d
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

Answer: a
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.
advertisement

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

Answer: d
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

Answer: d
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.
advertisement

10. Which of the following has maximum clique size 2?
a) Perfect graph
b) Tree
c) Histogram
d) Cartesian
View Answer

Answer: a
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

Answer: c
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

Answer: c
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

Answer: b
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

Answer: a
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

Answer: a
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.

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.