Past exam of the probability, statistics and options I course of the University of Oxford / 2011 / R / 1 / a

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\cdot 6-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_3{b}_3$ from the bipartition $\{a_1,a_2,a_3\}\bigsqcup \{b_1,b_2,b_3\}$. The left drawing below is a planar embedding of all eight remaining edges. It proves that the minimum is one edge.