 Bipartition of a graph

A bipartition of a graph divides its vertex set into two independent sets, so every edge joins different parts. A graph admitting such a partition of a set is a bipartite graph. The two parts are not generally unique: separate connected components of a graph can have their sides exchanged independently, and isolated vertices can be assigned to either part.