染色的条件相当于同色且有边相连的两个点至少有一个需要染红，但是因为可以选择一个团全部染红，这个条件并不好表示。

考虑枚举团当中的一个点 $x$，那么一个染红的点如果与 $x$ 相邻就在团中，否则就不在团中。因此限制可以写成如果 $u,v$ 不同时与 $x$ 相邻，则它们之间有边时不能同时染红；如果 $u,v$ 同时与 $x$ 相邻，则它们之间没有边时不能同时染红。这些条件都可以用 2-SAT 表示。

每次 2-SAT 需要在原图的基础上加上额外的 $O(\deg(x)^2)$ 条边，总和不会超过 $O(nm)$，因此总时间复杂度 $O(n(n+m))$。