About $K_{3,3}$ being planar or not

369 Views Asked by At

I wanted to propose a “proof” that graph $K_{3,3}$ is not planar. Lets suppose it is planar, then by Euler’s theorem $V-E+F=2$. Now since $V=6$ and edges $E=9$ , so $F=5$. Now there cannot be a 3-cycle, since in this case two vertices that were not supposed to be would be connected (this is not hard to prove but i will omit). Now $K_{3,3}$ is connected , since we can access to any vertice by jumping around(this is also not hard to prove i think). Now this graph must have cycles, since otherwise graph would be a tree but it isnt since $V-1$ aint $E.$ So there is a cycle , and this cycle must contain 2 vertices that are not connected directly to each other. There can be 3 choose 2 ways to form such cycles whcih means we would have 3 cycles which could produce 4 faces but we needed 5 faces, so that is contradictory.

1

There are 1 best solutions below

4
On

A fast argument to see that there are no $3$-cycles: $K_{3,3,}$ is bipartite, hence every face has an even number of edges, or at least four edges. After that, $F$ faces means at least $4F$ face-edge incidences, which means at least $2F$ edges. This already contradicts $E=9$ and the $F=5$ you obtained from Euler.