Example 16.1.
Even if Builder is constrained to build a path on \(4\) vertices, then Assigner can be forced to use three colors. At Round 1, Builder presents a vertex \(x\) and Assigner colors it. At Round 2, Builder presents a vertex \(y\) and declares that \(x\) and \(y\) are not adjacent.
Now Assigner has a choice. She may either give \(x\) and \(y\) the same color, or she may elect to assign a new color to \(y\text{.}\) If Assigner gives \(x\) and \(y\) different colors, then in Round 3, Builder presents a vertex \(z\) and declares that \(z\) is adjacent to both \(x\) and \(y\text{.}\) Now Assigner will be forced to use a third color on \(z\text{.}\) In Round \(4\text{,}\) Builder will add a vertex \(w\) adjacent to \(y\) but to neither \(x\) nor \(z\text{,}\) but the damage has already been done.
On the other hand, if Assigner \(x\) and \(y\) the same color, then in Round 3, Builder presents a vertex \(z\text{,}\) with \(z\) adjacent to \(x\) but not to \(y\text{.}\) Assigner must use a second color on \(z\text{,}\) distinct from the one she gave to \(x\) and \(y\text{.}\) In Round 4, Builder presents a vertex \(w\) adjacent to \(z\) and \(y\) but not to \(x\text{.}\) Assigner must use a third color on \(w\text{.}\)