Lesson 2

A bipartite graph is an undirected graph \(G(V,E)\) whose vertices can be divided into two parts \(V_{1}\) and \(V_{2}\) (\(V=V_{1} \sqcup V_{2}\)), such that every edge connects vertices from different parts (that is, for every \(\{u,v\} \in E\), it holds that \(|V_{1} \cap \{u,v\}|=1\)).

In many applications, a graph is given together with a partition and is denoted by \(G(V_{1} \sqcup V_{2}, E)\). Sometimes, \(V_{1}\) and \(V_{2}\) are called \(L\) and \(R\) and a graph is drawn with the nodes from \(L\) on the left and nodes from \(R\) on the right. Here is an example where it is visually clear that every edge joins two nodes from different parts.

Bipartite graphs often arise in practical applications where relationships between two different sets of objects need to be modeled. Here are just a few examples:

• men and women;


• buyers and goods;


• hospitals and patients;


• donors and people in need of organs;


• tasks and performers;


• advertisements and search queries;


• white and black cells on a board.