= Solution
{c}
The modified graph is \b[planar]. Place $x_1=(-2,0)$ and $x_2=(2,0)$, and place the other <vertices> on the vertical line between them in the bottom-to-top order $y_2,y_1,y_5,y_3,y_4$. Draw each edge $x_i y_j$ as a straight segment. Each half of the drawing is a fan sharing one endpoint, so its <edges> do not cross. The added <edges> $y_2y_1$ and $y_1y_5$ are consecutive vertical segments, meeting other <edges> only at their endpoints. The following original drawing exhibits the embedding.
\Image[/past-exam-of-the-probability-statistics-and-options-i-course-of-the-university-of-oxford/2010-modified-bipartite-graph.png]
{title=A planar embedding and a three-colouring of the modified complete bipartite graph}
Back to article page
