二分图

若无向图 G 的结点能够划分为两个子集 $V_1,V_2$，满足 $V_1\cap V_2=\varnothing$，使得所有边的两个端点分别在两个子集里

完全二分图

性质

• 不存在长度为奇数的回路，若所有回路的长度都为偶数，则一定是二分图
• 如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点（可以间隔着色）

充要条件

G 的所有回路的长度均为偶数：正着过去可以构造，反过来证明要用反证法，设有一个在子集里的连边，证明必然存在一个奇数的回路

若 G 不是连通图，那么就对每个 连通分支 重复上面的论证，可以得到相同的结论

完全匹配