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.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. (B) and (E) are incorrect
Explanation
Trees and bipartite graphs are 2-colourable (A, C true), and greedy colouring uses at most d + 1 colours (D true). Bipartite graphs have no odd cycles — even cycles are allowed — so B is wrong. A graph with O(|V|) edges can still contain a large clique, so E is wrong.
More Discrete Structures and Optimisation questions
- Consider the statement: A person who is radical (R) is electable (E) if he/she is conservative (C), but otherwise is not electable. Which o…
- Let R1 = {(1,1), (2,2), (3,3)} and R2 = {(1,1), (1,2), (1,3), (1,4)}. Match List I with List II. List I: A. R1 ∪ R2, B. R1 − R2, C. R1 ∩ R2…
- Find the lexicographic ordering of the bit strings 0 < 1 given below based on the ordering . (A) 001 (B) 010 (C) 011 (D) 0001 (E) 0101 Choo…
- Statement I: 5 divides n⁵ − n whenever n is a non-negative integer. Statement II: 6 divides n³ − n whenever n is a non-negative integer.
- A basic feasible solution of an transportation problem is said to be non- degenerate, if basic feasible solution contains exactly----------…
- Maximize z = x₁ + x₂ subject to x₁ + 2x₂ ≤ 2000, x₁ + x₂ ≤ 1500, x₂ ≤ 600, x₁, x₂ ≥ 0. The solution is