graph is bipartite if the vertices can be partitioned into two sets, X and Y, so that the only edges of the graph are between the vertices in X and the vertices in Y. Trees are examples of bipartite graphs. If G is bipartite, it is usually denoted by G = (X, Y, E), where E is the edge set.

a graph G whose vertex set consists of two disjoint sets, A and B, and whose edge set contains only edges with one vertex in A and one vertex in B

a graph where the vertex set can be decomposed into two subsets U and V such that each edge of G joins a vertex of U to a vertex of V