Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 38 / 4 / d / 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. ThusFor 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.