Course contentsShow
← Mathematics
Lesson 2693 of 3,12153. Graph TheoryFree lesson

K₅ and K₃,₃ are Non-Planar

Prove that the complete graph K₅ and complete bipartite graph K₃,₃ cannot be drawn without crossings.

K₅ and K₃,₃ are Non-Planar

What you'll learn: You'll prove that two famous graphs—K₅ (five vertices all connected) and K₃,₃ (complete bipartite with 3+3 vertices)—cannot be drawn on a plane without edges crossing.

The Core Idea

A planar graph can be drawn on a flat surface with no edge crossings. Some graphs, however, are inherently non-planar: no matter how cleverly you arrange the vertices, crossings are unavoidable. K₅ and K₃,₃ are the two fundamental examples.

Proving K₅ is Non-Planar

The complete graph K₅ has 5 vertices and every pair is connected, giving us 10 edges.

Using Euler's Formula (v - e + f = 2) and the consequence that for simple planar graphs with ≥3 vertices, e ≤ 3v - 6:

  • v = 5, so maximum edges = 3(5) - 6 = 9 edges
  • K₅ has 10 edges, which exceeds the bound
  • Therefore, K₅ cannot be planar

Proving K₃,₃ is Non-Planar

K₃,₃ is a bipartite graph with 3 vertices in each partition, fully connected across: 6 vertices, 9 edges.

For bipartite planar graphs (which have no triangles, only cycles of length ≥4), a stricter inequality holds: e ≤ 2v - 4:

  • v = 6, so maximum edges = 2(6) - 4 = 8 edges
  • K₃,₃ has 9 edges, which exceeds the bound
  • Therefore, K₃,₃ cannot be planar

Why This Matters

These two graphs are the "minimal obstructions" to planarity. Kuratowski's Theorem (beyond our current scope) states that any non-planar graph contains a subdivision of K₅ or K₃,₃—making them the fundamental building blocks of non-planarity.

Key Takeaway: K₅ and K₃,₃ are provably non-planar because they have too many edges relative to their vertices to satisfy the constraints imposed by Euler's formula and planar graph theory.