Question

What is the simplest method to prove that a graph is bipartite?

(a) It has a cycle of an odd length

(b) It does not have cycles

(c) It does not have a cycle of an odd length

(d) Both odd and even cycles are formed

The question was posed to me during an internship interview.

My question comes from Matching in section Matching of Data Structures & Algorithms II

Answer 1

Right option is (c) It does not have a cycle of an odd length

The best I can explain: It is not difficult to prove that a graph is bipartite if and only if it does not have a cycle of an odd length.