如果图 G=(V,E) 的顶点集 V 可以分为两个互不相交的子集 X 和 Y，使得每条边 e∈E 的两个端点都分别属于 X 和 Y，就称图 G 是一个 二分图（bipartite graph）。集合 X 和 Y 常称作它的两个 部分（part），或者分别称为二分图的左部和右部。当二分图的两个部分 X 和 Y 已知时，也可以用三元组 (X,Y,E) 来表示二分图 G。
一个典型的二分图如下图所示。
树、偶环、网格图等都是常见的二分图的例子。
刻画
二分图也可以由下列性质等价地定义：
图 G 是可 2‑着色的。也就是说，可以用至多两种颜色给图的所有顶点染色，并且保证相邻顶点颜色不同。
图 G 中不存在奇数长度的环。
很显然，第一条性质与二分图的定义等价：只需要将二分图的两个部分各染一种颜色就好了。
第二条性质稍微复杂一些。可以考虑用两种颜色尝试给图 G 染色。因为不同连通分量之间染色互不干扰，只需要逐个考虑连通分量就好了。任选连通分量中的一个顶点 s，进行 DFS，并记录连通分量中每个顶点 v 与 s 的距离。从 s 开始，在 DFS 生成树上进行归纳可知，如果存在一种可行的染色方法，一定是根据每个顶点 v 到起点 s 的距离的奇偶性分别染成两种颜色。
继而考虑那些不在生成树中的边。如果这些非树边的两个端点的颜色都不一样，就说明当前的染色方案可行；否则，就不存在可行的方案。进一步地，两个顶点颜色不同，当且仅当它们到树根 s 的距离一奇一偶，这又等价于加入该非树边形成的是一个偶环而非奇环。因此，只要没有奇环，这些非树边必然连接颜色不同的点，进而整张图都可以用两种颜色染色，图就一定是二分图。
int n;std::vector<std::vector<int>> gr;std::vector<int> colors, vis;// Depth-first search to color vertices.bool dfs(int cr) { vis[cr] = true; for (int nt : gr[cr]) { if (vis[nt]) { if (colors[cr] == colors[nt]) return false; } else { colors[nt] = colors[cr] ^ 1; if (!dfs(nt)) return false; } } return true;}// Check whether the graph GR is bipartite.// If so, the vector COLORS will store a feasible coloring.bool check_bipartite() { for (int i = 1; i <= n; ++i) { // Check connected components one by one. if (!vis[i]) { colors[i] = 0; if (!dfs(i)) return false; } } return true;}