Graph is bipartite if the nodes can be split into two disjoint sets such that there is no edge between nodes inside the same set.