A graph is bipartite iff it does not contain any odd length cycle. We can use DFS algorithms and whenver there is back edge we need to make an extra assertion whether it create an odd length cycle or not. Simple way to implement is to give visited nodes a label 1 and 2 alternatively i.e if current node has label 1, give label 2 to next neighbour of current node. If back is from node of some label to node with same label then its making odd length cycle.