## Problem1D

Problem 1D: The complete bipartite graph ${K_{n,m}}$ has ${ n+m}$ vertices ${a_{1},\ldots ,a_{n}}$ and ${b_{1},\ldots ,b_{m},}$ and as edges all ${mn}$ pairs ${\left\{ a_{i},b_{j}\right\} .}$ Show that ${K_{3,3\text{ }}}$is not planar.

Solution: Euler’s formula states that for a drawing of a connected planar graph on the plane, ${f-e+v=2}$, where ${f,e}$ and ${v}$ are, respectively, the numbers of faces, edges, and vertices. If ${K_{3,3}}$ is planar, ${f-9+6=2,}$ thus ${f=5.}$ On the other hand, each face in a bipartite graph has at least four border edges, and each edge shares two faces. Hence there would be at least ${\frac{4f}{2}=10}$ edges in the graph, contradicts to the number of edges of ${K_{3,3}.}$

Notes: By the hints of problem 1D, the author tells to show there are only one drawing in some sense if we omit one point of ${K_{3,3}}$, and just considering the remaining 6 edges. But in what sense? I am curious for the exact explanation.