User BFS for same, while traversing through nodes label the first visited node as 0, label its neighbors as 1. if you get a label 1 node, label its unlabelled neighbors as 0. at any point if you get an already labelled neighbor as 0 - 0 ( you get label 0 neighbor from label 0 node) or 1 - 1(respectively) the graph is not bipartite