= Solution
\b[This is a <graph colouring> <constraint satisfaction problem>, with four available colours and one fixed colour.] Interpret slot labels as colours. Every conflict <edge> requires distinct endpoint colours, exactly as in <proper graph colouring>; <independent sets> of <vertices> can share a slot. The unary restriction on $A$ fixes its colour to $1$.
The lecture's 3-colouring problem is the same construction with domains $\{1,2,3\}$. For the present <graph> under the assumptions in (a), the <clique> $\{A,B,E,G\}$ prevents a 3-colouring, while (c) supplies a 4-colouring. The fixed colour on $A$ does not otherwise change existence, since an unconstrained colouring can have its colour names permuted to put $A$ in colour $1$.
This four-colour necessity is conditional on the explicit $EA$ overlap. Removing that one <edge> permits, for example, the 3-colouring $(A,B,C,D,E,F,G)=(1,2,2,3,1,2,3)$; the four-slot schedule remains valid in either model. Thus attendee modelling, rather than the mere availability of four slots, determines the required number of colours.
Back to article page
