##### Example16.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\). 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\). Now Assigner will be forced to use a third color on \(z\). In Round \(4\), Builder will add a vertex \(w\) adjacent to \(y\) but to neither \(x\) nor \(z\), 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\), with \(z\) adjacent to \(x\) but not to \(y\). Assigner must use a second color on \(z\), distinct from the one she gave to \(x\) and \(y\). In Round 4, Builder presents a vertex \(w\) adjacent to \(z\) and \(y\) but not to \(x\). Assigner must use a third color on \(w\).