Topics: Graph - Graph Theory


A bipartite graph is a graph whose set of vertices can be partitioned in two subsets and , such that every edge of joins a vertex in and another one in .

The pair is called a bipartition of , and are called the subsets of the bipartition.

As the name suggests, a bipartite graph’s partition only contains two subsets.

We can also have complete bipartite graphs.



A bipartite graph can’t have any loops.


The smallest simple graph that is not bipartite is the complete graph.