二分图有关的都放在这里。
A：图G是二分图
B：图G中不存在奇数环
C：图G可以进行染色
注：染色法：对于每一条边 \((u, v)\)，u和v应染成不同的颜色（放入两个点集），遍历每一条边看下是否有矛盾即可（具体来说，从1个点出发dfs，如果两个点中有一个未染色，就染成符合条件的颜色，否则检查是否为不同颜色）。
下面证明 \(A \iff B \iff C\)。
- \(B \Rightarrow C\)
假设图G不能进行染色，也就是说染色过程中出现了矛盾。
点u和v都被染色了，说明它们都被遍历过了，也就是在一个连通块中。
又因为之前的染色没有矛盾，所以它们之间存在至少一条合法路径，是黑白黑白...
加上这条矛盾边后，这些合法路径都变成一个环。
也就是我们找到了一条边：
由于起点是黑，终点是黑，所以路径长度必然是奇数，这也就说明了存在一个奇数环，与\(B\)矛盾，假设不成立。
故\(C\)。
- \(B \Leftarrow C\)
假设图G存在奇数环。
将这个环染色，必然出现首尾颜色相同的情况，也就是染色一定失败，与 \(C\) 矛盾，假设不成立，所以 \(B\)。
至此，已经证明了 \(B \iff C\)
PS：这里用反证法是对的，但其实这里的反证法是用了\(\neg q \Rightarrow \neg p\)，则\(p \Rightarrow q\)。