Bipartite Graph

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent. In other words, all edges in the graph connect a vertex from one set to a vertex in the other set.

Formally, a graph G = (V, E) is bipartite if and only if its vertex set V can be partitioned into two sets V1 and V2 such that every edge in E connects a vertex in V1 to a vertex in V2.

Bipartite graphs are often used to model relationships between two distinct groups of objects or entities. For example, a bipartite graph could be used to model the relationship between students and classes, where one set of vertices represents students and the other set represents classes, and edges represent enrollment.

Bipartite graphs have several interesting properties, including the fact that they do not contain any odd cycles. This makes them useful in a variety of applications, including network flow problems and matching problems.