What is a bipartite graph?

A bipartite graph, also known as a bigraph, refers to a graph whose vertex set can be divided into two independent sets. The division is done in such a way that each edge of the graph connects a vertex in the first set to a vertex in the second set.

These graphs are used in modeling relationships between two different classes of object. For instance, it is used to map the relationship in an affiliation network where new users are related to older ones. A graph is said to be bipartite if it does not contain an odd cycle, its chromatic number is equal to or less than two and its spectrum is symmetric.