A graph is bipartite when the graph vertices are parted into two disjoint sets; no two adjacent vertices would reside in the same set. A bipartite graph must not contain odd cycle (a cycle with an odd number of vertices).
- BFS (Breadth First Search) can be used in detecting a bipartite graph.
- Another method of checking a bipartite graph is to check the occurrence of an odd cycle in the graph.