Planar Graphs and Euler's Formula

Imagine you are designing a circuit board. Little components sit on the board and copper tracks must connect them — but two tracks that touch would short the circuit. So you keep asking the same question: can I draw all these connections on one flat layer with no wire crossing another? A graph you can draw that way is called planar, and it is one of the most beautiful ideas in graph theory.

A planar graph is a graph that can be drawn in the plane so that no two edges cross. That drawing does something wonderful: the edges slice the plane into regions, called faces. And no matter how you draw it, the vertices, edges and faces always obey one astonishingly simple law — V - E + F = 2 — discovered by Leonhard Euler.

Planar is about can, not looks

Here is the subtle part that trips everyone up. A graph is planar if some drawing has no crossings — even if the drawing in front of you is a tangled mess. The square with both diagonals looks crossed, yet you can redraw it with one diagonal bulging outside, and suddenly nothing crosses. Planarity is a property of the graph, not of one particular picture of it.

Once you have a crossing-free drawing (a plane embedding), count the regions it cuts the paper into. Do not forget the big region that stretches out forever around the whole figure — the outer, or unbounded, face. It counts just like all the others.

Watch the faces appear

Below is a small connected planar graph. Step through to reveal its faces one at a time — first the bounded inner regions, then the all-important outer face — and see Euler's count fall out.

The pattern is universal. For any connected graph drawn in the plane with no crossings:

For a connected planar graph with V vertices, E edges and F faces (the outer face included),

V - E + F = 2.

Two quick checks

A single triangle. Three corners, three sides, and two faces — the inside and the outside:

V - E + F = 3 - 3 + 2 = 2. \checkmark

The cube graph. Flatten a cube onto the page (push the top face down inside the bottom one) and nothing has to cross. A cube has V = 8 corners and E = 12 edges, so Euler forces

F = 2 - V + E = 2 - 8 + 12 = 6,

and indeed a cube has 6 faces. The formula predicted the answer before we even looked. Notice the handy rearrangement F = 2 - V + E: once you know two of the three numbers, Euler hands you the third.

A budget on edges

Euler's formula has teeth. In a simple planar graph (no loops, no repeated edges) with V \ge 3, every face is bounded by at least 3 edges, and each edge borders 2 faces. Counting edge-sides two ways gives 2E \ge 3F. Feed that into V - E + F = 2 and you land on a famous inequality:

Any simple planar graph with V \ge 3 vertices has at most

E \le 3V - 6

edges. A graph with more edges than this cannot be planar.

This is a planarity detector. Count vertices and edges; if E blows past 3V - 6, no crossing-free drawing can possibly exist.

Two graphs that refuse to lie flat

Take K_5: five vertices with an edge between every pair. That is 10 edges. But 3V - 6 = 3(5) - 6 = 9. Since 10 > 9, the edge budget is busted — K_5 is not planar, and no amount of clever redrawing will save it.

Its twin is K_{3,3}: two groups of three vertices, every vertex in one group joined to every vertex in the other. It is also non-planar (its faces would need \ge 4 edges each, giving the sharper bound E \le 2V - 4 = 8, yet it has 9 edges). These two, K_5 and K_{3,3}, are the fundamental obstructions: Kuratowski's theorem says a graph is planar exactly when it hides neither of them inside.

There is a classic puzzle — the three utilities problem. Draw three houses and three utilities (gas, water, electricity). Can you connect every house to all three utilities without any pipes crossing? People try for hours. It is impossible — and now you can prove it in one line: that connection pattern is K_{3,3}, and K_{3,3} is non-planar. The puzzle isn't hard; it's flat-out unsolvable, and Euler's formula is the referee that says so.

Every convex polyhedron, flattened onto the plane, becomes a connected planar graph — so it obeys V - E + F = 2 too. Check the five Platonic solids: the tetrahedron (4 - 6 + 4 = 2), the cube (8 - 12 + 6 = 2), the octahedron (6 - 12 + 8 = 2), the dodecahedron (20 - 30 + 12 = 2), the icosahedron (12 - 30 + 20 = 2). All of them land on 2. In fact Euler's formula is exactly what lets you prove there are only five Platonic solids — no sixth is geometrically possible.

Two traps snap shut here. First: "K5 can't be planar because it looks crossed." A messy, crossing-filled picture proves nothing — planarity asks whether some crossing-free drawing exists, not whether your first attempt had crossings. (The square-with-diagonals looks crossed but is planar!) The real reason K_5 fails is the edge budget: 10 > 3V - 6 = 9.

Second: forgetting the outer face. When you count F, the unbounded region wrapping around the whole figure is a face too. A triangle has 2 faces, not 1. Miss the outer face and Euler's formula "breaks" — but it was your count, not Euler, that was wrong.

Special case: a tree

A tree is a connected graph with no cycles. Drawn in the plane it never encloses any region, so it has just one face — the outer one. Check Euler: a tree on V vertices has E = V - 1 edges, so

V - E + F = V - (V - 1) + 1 = 2. \checkmark

Even the humblest connected graph obeys the law.