= Solution
{c}
The <complete bipartite graph> $K_{3,3}$ is not a <planar graph>. For example, a simple connected triangle-free planar graph with six vertices has at most $2\cdot6-4=8$ edges, by <Euler formula for a connected planar graph> and the fact that every face has boundary length at least four; $K_{3,3}$ has nine edges. At least one edge must therefore be deleted.
Delete $a_3b_3$ from the bipartition $\{a_1,a_2,a_3\}\sqcup\{b_1,b_2,b_3\}$. The left drawing below is a planar embedding of all eight remaining edges. It proves that \b[the minimum is one edge].
\Image[/past-exam-of-the-probability-statistics-and-options-i-course-of-the-university-of-oxford/2011-planar-graphs.png]
{title=Left: a planar embedding of K3,3 with edge a3b3 removed. Right: K2,3, whose two bounded faces and exterior give three faces in total.}
Back to article page
