# Boolean formula for graph 3COL

For a given undirected graph $$G=(V,E)$$ I'm trying to construct a boolean polynomially computable formula $$\varphi$$ with the following property: $$\varphi$$ is satisfiable $$\iff$$ vertices of $$G$$ can be colored in $$3$$ colors with the following condition: For any edge $$(u, v)\in E$$, if $$u$$ and $$v$$ have different colors, then there exists $$w\in V$$ such that $$(u, w)\in E$$, $$(v, w)\in E$$, and $$w$$ has the third color (different from both $$u$$ and $$v$$). Here it is ok that two vertices of the same color may be connected by an edge.

• Are you looking for a coloring in the standard sense? I.e., the endpoints of each edge must have different colors? Oct 6, 2021 at 11:29
• @Steven Not in the traditional sense, two endpoints of edge may have the same color
– Andy
Oct 6, 2021 at 11:33

Here is one possible formula: $$\texttt{true}$$. Indeed, every graph admits a coloring that satisfies your requirements: simply color all vertices with the same color.
• Thanks. But if we color all vertices with the same color, the condition "For any edge $(u, v)\in E$, if $u$ and $v$ have different colors, there exists..." never happens?
• That condition because trivially true since there are no edges $(u,v)$ that satisfy the requirements. Essentially, you are using an universal quantifier over an empty set. Oct 7, 2021 at 9:22