A bipartite graph G = (V, E) is a graph whose vertex set V can be partitioned into two disjoint sets X and Y such that every edge in E has one endpoint in X and the other in Y. Informally, a graph is bipartite if we can color its vertices red or black such that each edge connects a red vertex to a black vertex.
If G is bipartite, then it cannot contain any odd-length cycles. In fact, the converse is also true. If a graph G does not contain any odd-length cycles, then it is bipartite. Thus, odd cycles are the only obstacle to bipartiteness.
We can determine whether a graph is bipartite in linear time by doing a single BFS or DFS traversal. The pseudocode below checks bipartiteness with BFS.
Take a look at C++ implementation.
Try your hand at problem BUGLIFE which uses this idea.
Reference: Algorithm Design by Kleinberg and Tardos