Bipartite

Summary

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that the vertices in one set are not connected to each other, but may be connected to vertices in the other set. Put another way, a bipartite graph is a graph with no odd cycles; equivalently, it is a graph that may be properly colored with two colors. Bipartite graphs are often written $G = (U,V,E)$ where $U$ and $V$ are the subsets of vertices of each color. However, unless the graph is connected, it may not have a unique 2-coloring.