Planar Graphs

Planar graphs are graphs that can be drawn in the plane without edge crossings.

Planar vs plane

• A planar graph is an abstract graph that admits a crossing-free drawing.
• A plane graph is a specific crossing-free drawing (an embedding) of a planar graph.

In an embedding, the edges partition the plane into faces (regions), including the outer face.

Faces and counting

For a connected plane graph, if

• $V$ = number of vertices,
• $E$ = number of edges,
• $F$ = number of faces (including the outer face),

then Euler's formula says:

$V - E + F = 2.$

This simple invariant powers many classic non-planarity arguments and extremal bounds.

Typical proof moves

• Subdivide edges (replace an edge by a path): preserves planarity.
• Add/remove an edge while tracking whether it creates a crossing; in planar proofs, it’s common to remove a non-bridge edge to keep the graph connected.
• Triangulate a connected plane graph (add edges inside faces until every face is a triangle) to derive sharp edge bounds.

Where to go next

• Euler's Formula
• Kuratowski's Theorem