Proof that $K_{3,3}$ is non planar using Euler's formula.

1.1k Views Asked by At

I'm struggling to understand the proof that $K_{3,3}$ is nonplanar. Using Euler's formula we know that $3f \leq 2e$. The proof goes like this: If we had drawn the graph in the plane, there would be no triangles: this is because in any triangle either two wells or two houses would have to be connected, but that is not possible. So, summing up the sides of every face we get $4f \leq 2e$. I don't understand where the 4f comes from.

Why is it that every face has at least four edges?

1

There are 1 best solutions below

5
On

As $K_{3,3}$ is a bipartite graph, each face is bounded by an even number of edges, so at least four. If there are $f$ faces, then the total number of edges in their boundaries is $\ge 4f$, but that total number is $2e$ as each edge is in two faces, so $2e\ge 4f$.