= Solution
Name the upper <graph triangle>'s vertices $a,b,c$, where $b$ is adjacent to $x$ and $c$ to $y$. Name the middle left vertex $d$ and the lower right vertex $e$. Then $a$ is adjacent to $d$, the lower <graph triangle> is $d,t,e$, and $e$ is adjacent to $z$.
Suppose $x,y,z$ all have colour $F$, while $t$ has a different colour $T$; denote the third colour by $B$. In the upper <graph triangle>, $b$ and $c$ cannot have colour $F$ and are adjacent, so they have colours $T,B$ in some order and $a$ has colour $F$. In the lower <graph triangle>, $e$ is adjacent to both $t$ and $z$, forcing $e$ to have colour $B$, and then $d$ must have colour $F$. But the edge $ad$ now has equal-coloured endpoints, a contradiction. Thus
$$
\boxed{c(x)=c(y)=c(z)\ne c(t)\text{ cannot occur}.}
$$
For the <three-colour clause gadget> used in a reduction, one also needs the converse extension property for Boolean-coloured inputs. With $t=T$ and $x,y,z\in\{T,F\}$, every tuple other than $(F,F,F)$ extends. If $x=T$, take $(a,b,c,d,e)=(T,F,B,F,B)$; this works regardless of $y,z$. If $x=F,y=T$, take $(T,B,F,F,B)$. Finally, if $x=y=F,z=T$, take $(F,T,B,B,F)$. Each assignment satisfies every edge. Therefore this <three-colour clause gadget> realizes exactly a three-input disjunction on Boolean inputs.
Back to article page
