a non-bipartite graph, such as a triangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.

One often writes to denote a bipartite graph whose partition has the parts and , with denoting the edges of the graph. If a bipartite graph is not connected, it may have more than one bipartition; in this case, the notation is helpful