Is K3,3 planar?

Planar graph

A graph is planar if it can be drawn in the plane without any two edges crossing (edges meet only at vertices).

K₃,₃ is not planar

K₃,₃ has two sets of 3 vertices with all 9 edges between them (the "three houses, three utilities" problem). It has v = 6, e = 9, and no triangles (it is bipartite, so there are no odd cycles).

   u1   u2   u3
    |\ /| \ /|        every u is joined
    | X | / \|        to every w (9 edges)
   w1   w2   w3

Reason 1 (Euler's formula). Suppose K₃,₃ were planar. Then v − e + f = 2 gives f = 2 − 6 + 9 = 5 faces. Every face is bounded by a closed walk of at least 4 edges (no triangles), and every edge borders at most two faces, so 2e ≥ 4f. But 2e = 18 and 4f = 20, so 18 ≥ 20, a contradiction.

Reason 2 (edge bound). A simple connected planar graph with no triangles satisfies e ≤ 2v − 4. For K₃,₃: 2v − 4 = 8, but e = 9 > 8.

Reason 3 (Kuratowski's theorem). A graph is planar if and only if it has no subgraph that is a subdivision of K₅ or K₃,₃. K₃,₃ is itself K₃,₃, so it is non-planar.

Hence K₃,₃ is not planar. (K₃,₂ and K₂,ₙ are planar, but K₃,₃ is the smallest non-planar bipartite graph.)