K₅ and K₃,₃ are Non-Planar

Graph Theory · Axiom Academy

LESSON K₅ and K₃,₃ are Non-Planar Proving two fundamental graphs cannot be drawn without edge crossings The complete graph K₅ has 5 vertices with every pair connected. Let's count its properties and see why it can't be planar. Assume K₅ is planar. For any simple planar graph with V ≥ 3: Since 10 > 9, our assumption is false. K₅ cannot be planar. K₃,₃ is a complete bipartite graph: 3 vertices on each side, with each vertex on one side connecting to all vertices on the other side. Proof using Bipartite Property: For bipartite planar graphs, we have a stronger bound (no triangles exist, so each face has ≥4 edges): Since 9 > 8, K₃,₃ cannot be planar. 3. Why Crossings are Unavoidable Let's try to draw K₅ without crossings. No matter how we arrange the vertices, we'll always need at least one crossing.

This is the written version of the interactive lesson above. See the full Graph Theory course.