What is the chromatic number of an n vertex simple connected graph which does not contain any odd length cycle? Assume n...

Question

What is the chromatic number of an n vertex simple connected graph which does not contain any odd length cycle? Assume n >= 2.

A. 2
B. 3
C. n = 1
D. n

Accepted Answer

2 A graph contains no odd-length cycle if and only if it is bipartite. A bipartite graph splits its vertices into two independent sets, and you only need two colours — one for each side. Since the graph is connected and has at least 2 vertices, it definitely needs at least 2 colours, so the answer is exactly 2.

What is the chromatic number of an n vertex simple connected graph which does not contain any odd length cycle? Assume n >= 2. A. 2 B. 3 C. n = 1 D. n