**Problem 1D: The complete bipartite graph **** has **** vertices **** and **** and as edges all **** pairs **** Show that ****is not planar.**

**Solution: **Euler’s formula states that for a drawing of a connected planar graph on the plane, , where and are, respectively, the numbers of faces, edges, and vertices. If is planar, thus 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 edges in the graph, contradicts to the number of edges of

**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 , and just considering the remaining 6 edges. But in what sense? I am curious for the exact explanation.

### Like this:

Like Loading...

*Related*