Skip to main content

For questions about graphs for which the set of vertices can be divided into two disjoint subsets such that no edge of the graph joins two vertices from same subset.

A bipartite graph is a graph $G=(V,E)$ such that the vertex set $V$ can be divided into two disjoint subsets such that no edge of $G$ joins two vertices from same subset. That is, $V=V_1\cup V_2$ such that $V_1\cap V_2=\emptyset$ and for any $e=uv\in E$, one of vertices among $u$ and $v$ belongs to $V_1$ and another belongs to $V_2$. There is no edge $e=uv\in E$ such that both $u$ and $v$ belongs to $V_1$ or both belongs to $V_2$.