Describe 3-colourable graph in propositional calculus I am trying to solve the following problem.
Let $G=(V,E)$ be a Graph with $V=N$ (natural numbers) and $p_{ij}$ a set of propositional variables for which we have $p_{ij}$ is true <=> $(i,j)\in E$.
I need a set of propositional formulas $\Psi$ based on $p_{ij}$ which have the following property: $\Psi$ are all true $\iff$ $G$ is 3-colourable.
My idea is: $G$ is not 3-colourable if and only if there are $i,j,k,l$ from $V$, so that $(i,j),(j,k),(i,k),(i,l),(j,l),(k,l)$ are all in $E$.
So $\Psi$ would consist of the formulas $\neg (p_{ij} \land p_{jk} \land p_{ik}\land p_{il}\land p_{jl}\land p_{kl})$.
But I'm not sure, it seems somewhat too simple for me.
Could someone help me please?
 A: According to the De Bruijn–Erdős theorem, a graph $G$ is $3$-colourable if and only if every finite subgraph of $G$ is $3$-colourable. Hence, if $V(G)=\mathbb N=\{1,2,3,\dots\},$ then $G$ is $3$-colourable if and only if, for every $n,$ the subgraph $G_n$ induced by $\{1,2,3,\dots,n\}$ is $3$-colourable. I'm sure you can figure out how to construct a formula $\psi_n$ which is true if and only if $G_n$ is $3$-colourable. Then $\Psi=\{\psi_n:n\in\mathbb N\}$ is the set you want.
On second thought, after reading your comment, I'm not so sure you can figure out how to construct a formula $\psi_n$ which is true if and only if $G_n$ is $3$-colourable. Here's one way to construct such a formula. Consider a fixed number $n$ and let $[n]=\{1,2,3,\dots,n\}.$
For each set $X\subseteq[n]$ construct a formula $\alpha_X$ which says that $X$ is independent, i.e., that no two vertices in $X$ are joined by an edge. For example, if $X=\{2,3,5,7\},$ we can take
$$\alpha_X=\neg(p_{2,3}\vee p_{2,5}\vee p_{2,7}\vee p_{3,5}\vee p_{3,7}\vee p_{5,7}).$$
Next, for each partition $\pi$ of $[n]$ into three disjoint sets $R,B,G,$ construct a formula $\beta_\pi$ which says that we get a proper colouring of the graph $G_n$ if we colour the vertices in $R$ red, the vertices in $B$ blue, and the vertices in $G$ green; in other words, $\beta_\pi$ says that $R,B,G$ are independent sets. For example, if $n=9$ and $\pi=\{\{1,3,5,7\},\{2,9\},\{4,6,8\}\},$ we can take
$$\beta_\pi=\alpha_{\{1,3,5,7\}}\wedge\alpha_{\{2,9\}}\wedge\alpha_{\{4,6,8\}}.$$
Finally, list all the partitions of $[n]$ into three parts in a sequence $\pi_1,\pi_2,\dots,\pi_{k(n)}$ where $k(n)$ is the number of such partitions, and let
$$\psi_n=\beta_{\pi_1}\vee\beta_{\pi_2}\vee\cdots\vee\beta_{\pi_{k(n)}}.$$
Of course, the construction of the formulas $\psi_n$ is trivial. The nontrivial part of the problem is the De Bruijn–Erdős theorem; you can find a proof of that at the Wikipedia page.
