Mathematics.

graph structures

Euler's Formula for Planar Graphs

Graph Theory25 minDifficulty5 out of 10

You should know: planar graphs

Overview

Euler's formula states that for any connected graph drawn in the plane without edge crossings, the vertices, edges, and faces (regions the drawing divides the plane into, including the single unbounded outer face) always satisfy V − E + F = 2. Euler stated the polyhedral version of this in a 1750 letter to Goldbach (giving V − E + F = 2 for the vertices, edges, and faces of any convex polyhedron), and the same identity applies unchanged to any connected planar graph drawing, since a convex polyhedron's surface can always be flattened into a planar graph. The formula is the single most useful counting tool for planar graphs: it forces the edge bounds that prove K5 and K3,3 are non-planar, it constrains how many faces a map or circuit layout can have, and its invariance under different planar drawings of the SAME graph shows that V − E + F is a genuine topological property, not an artifact of how you happen to draw it.

Intuition

Start with a single point (V=1, E=0, F=1 — just the outer face): V-E+F = 1-0+1 = 2. Now build up any connected planar graph one edge at a time. Adding an edge between two EXISTING vertices always closes off a new region, splitting one face into two: E goes up by 1, F goes up by 1, so V-E+F is unchanged. Adding an edge out to a brand-new vertex extends the graph without enclosing anything: V goes up by 1, E goes up by 1, F stays the same, so V-E+F is unchanged again. Since both ways of growing the graph preserve V-E+F, and the single point starts at 2, every connected planar graph built this way must also equal 2 — an inductive proof disguised as bookkeeping.

Formal Definition

Definition

For a connected planar graph G drawn in the plane with V vertices, E edges, and F faces (regions of the plane, including the unbounded outer region):

V−E+F=2V - E + F = 2
Euler's formula (connected planar graphs)
V−E+F=1+C(C=number of connected components)V - E + F = 1 + C \quad (C = \text{number of connected components})
Generalization to disconnected planar graphs

Worked Examples

  1. Substitute V=8, E=12, F=6 into V - E + F.

    8−12+68 - 12 + 6

  2. Evaluate.

    8−12+6=28 - 12 + 6 = 2

Answer: 8 - 12 + 6 = 2, confirming Euler's formula for the cube.

Practice Problems

Difficulty 4/10

A regular dodecahedron has 20 vertices and 12 pentagonal faces. Use Euler's formula to find the number of edges.

Difficulty 3/10

A connected planar graph has 7 vertices and 9 edges. How many faces does it have?

Difficulty 6/10

A single-layer circuit board design has 15 component pads (vertices) connected by 22 non-crossing wire traces (edges), forming a connected planar layout. The designer wants to know how many enclosed regions (including the outer boundary) the layout carves the board into, to plan copper-pour zones. Use Euler's formula.

Quiz

Euler's formula for a connected planar graph states that V, E, and F (including the outer face) satisfy:
A convex polyhedron has 12 vertices and 30 edges. By Euler's formula, how many faces does it have?
For a planar graph with C connected components (not necessarily connected), Euler's formula generalizes to:

Summary

  • For any connected planar graph drawing, V - E + F = 2, where F counts all regions including the unbounded outer face.
  • Euler stated the polyhedral version in 1750; it applies to any convex polyhedron's flattened graph.
  • The formula can be proved inductively by building the graph edge-by-edge and checking V-E+F is invariant at each step.
  • It generalizes to disconnected planar graphs as V - E + F = 1 + C, where C is the number of components.
  • Euler's formula is the key tool behind the edge bounds (E ≤ 3V-6) used to prove K5 and K3,3 are non-planar.

References

  1. WebsiteWikipedia — Euler characteristic
  2. WebsiteWikipedia — Planar graph