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.
Everything Under The Sun 