NTA UGC NET Aug 2024 Paper-2
January 23, 2025Computer-Organization
January 25, 2025GATE 2009
|
Question 2
|
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2.
|
2
|
|
|
3
|
|
|
n-1
|
|
|
n
|
Question 2 Explanation:
If n≥ 2 and there are no odd length cycles, then it is a bipartite graph.
A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
Correct Answer: A
Question 2 Explanation:
If n≥ 2 and there are no odd length cycles, then it is a bipartite graph.
A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.
A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2.