Planar Graph — Definition, Formula & Examples

A planar graph is a graph that can be drawn on a flat surface so that none of its edges cross each other. Every drawing might look tangled, but if at least one crossing-free arrangement exists, the graph is planar.

A graph $G = (V, E)$ is planar if there exists an embedding of $G$ in the Euclidean plane $\mathbb{R}^2$ such that its edges intersect only at their common vertices. Such a crossing-free embedding is called a plane graph.

Key Formula

V - E + F = 2

Where:

$V$ = Number of vertices in the connected plane graph
$E$ = Number of edges
$F$ = Number of faces, including the outer (unbounded) face

How It Works

To check whether a simple graph might be planar, start with Euler's formula: for any connected plane graph,

V - E + F = 2

, where

V

E

, and

F

are the numbers of vertices, edges, and faces (including the unbounded outer face). A useful corollary is that every simple planar graph satisfies

E \leq 3V - 6

. If your graph has more edges than this bound allows, it cannot be planar. Two classic non-planar graphs are

K_5

(the complete graph on 5 vertices) and

K_{3,3}

(the complete bipartite graph with parts of size 3). By Kuratowski's theorem, a graph is planar if and only if it contains no subdivision of

K_5

K_{3,3}

Worked Example

Problem: Determine whether the complete graph

K_4

(4 vertices, each connected to every other) is planar, and verify Euler's formula for it.

Count vertices and edges:

K_4

has 4 vertices. The number of edges in a complete graph on

n

vertices is

\binom{n}{2}

E = \binom{4}{2} = 6

Check the edge bound: For a simple planar graph,

E \leq 3V - 6

. Substituting

V = 4

6 \leq 3(4) - 6 = 6

Verify Euler's formula: Draw

K_4

as a triangle with one vertex inside, connected to all three corners. This gives no crossings. Count the faces: 3 inner triangular regions plus 1 outer face, so

F = 4

V - E + F = 4 - 6 + 4 = 2 \checkmark

Answer:

K_4

is planar. It satisfies both the edge bound (

6 \leq 6

) and Euler's formula (

4 - 6 + 4 = 2

Why It Matters

Planar graphs appear in circuit board design, where wires on a single layer must not cross. They are also central to map coloring problems — the Four Color Theorem guarantees that any planar graph can be vertex-colored with at most four colors. In computer science courses, planarity testing is a key topic in algorithm design.

Common Mistakes

Mistake: Concluding a graph is non-planar because one particular drawing has crossings.

Correction: A graph is non-planar only if no possible drawing avoids crossings. Try rearranging vertices before concluding, or use the edge bound

E \leq 3V - 6

or Kuratowski's theorem.