An undirected graph where vertices can be partitioned into two sets such that no edge connects vertices in the same set.