Question about proof that $K_{3,3}$ is not a planar graph

58 Views Asked by At

I'm reading a proof of the fact that $K_{3,3}$ is not a planar graph, which uses the Euler formula $v-e+f=2$.

This is the proof presented in my lecture notes (which are based on, but not identical to, certain excerpts from Diestel's Graph Theory):

Suppose that, to the contrary, $K_{3,3}$ is planar. If $F$ is an arbitrary face (i.e. region) bounded by $K_{3,3}$, then $F$ is bounded by a cycle, and since $K_{3,3}$ is bipartite, it must be of even length, so its boundary is of length at least $4$. From there, we have $2e \geq 4f$, where $e$ is the number of edges of $K_{3,3}$, and $f$ the number of faces bounded by $K_{3,3}$, and since $v-e+f=2$, $v=6$, $e=9$, we have $f=5$, and so $9 \geq 10$, which is a contradiction.

Now, the part that's unclear to me is the conculsion that $F$ must be bounded by a cycle. I know that every bounded face must be bounded by a cycle, but I don't know that the unbounded face is bounded by a cycle.

This image is impossible, I assume, because there is a cycle of odd length here; but this is an example where the boundary of the unbounded face of a planar graph is not a cycle.

The part that I failed to emphasize: there is a proposition in Diestel which says that every face of a 2-connected graph is bounded by a cycle - however, there is a note in my lecture notes that the fact that $F$ is bounded by a cycle can be proven without this. Is there an easy answer to this dilemma?