Aspire's Library
A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
Consider the following statements:
(A) Any tree is 2-colorable
(B) A graph G has no cycles of even length if it is bipartite.
(C) A graph G is 2-colorable if it is bipartite.
(D) A graph G can be colored with d+1 colors if d is the maximum degree of any vertex in the graph G.
(E) A graph G can be colored with O(log|V|) colors if it has O(|V|) edges.
Choose the correct answer from the options given below:
(A) Any tree is 2-colorable
(B) A graph G has no cycles of even length if it is bipartite.
(C) A graph G is 2-colorable if it is bipartite.
(D) A graph G can be colored with d+1 colors if d is the maximum degree of any vertex in the graph G.
(E) A graph G can be colored with O(log|V|) colors if it has O(|V|) edges.
Choose the correct answer from the options given below:
Solution
(A) True, because every tree is bipartite, so it is 2-colorable.(B) False, because a bipartite graph has no odd cycle, but it can have even cycles.
(C) True, because every bipartite graph is 2-colorable.
(D) True, by greedy coloring, any graph with maximum degree $d$ can be colored using at most $d+1$ colors.
(E) False, because having $O(|V|)$ edges does not guarantee coloring with only $O(\log |V|)$ colors.
So, incorrect statements are (B) and (E).
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Ask Your Question or Put Your Review.
