greatitself.
Continue
core25 min studyLesson 219 in Mathematics

Planar graphs and Euler's formula

Separate a crossing-heavy drawing from nonplanarity, count faces correctly, and derive edge bounds from boundary incidences.

Before you begin
On this page

The question for today

What you’ll understand

  • Distinguish a planar graph from a chosen plane embedding.
  • Prove Euler's formula using a spanning tree and cycle-edge deletion.
  • Use simple and triangle-free planar edge bounds as necessary conditions.

A drawing with crossed edges does not prove that a graph is nonplanar; another drawing may remove the crossings. Planarity asks whether some embedding in the plane exists with edges meeting only at shared endpoints. Once such an embedding is fixed, its faces supply new countable objects. Euler's formula relates these regions to vertices and edges and turns geometric intuition into rigorous obstructions.

An embedding supplies faces

A planar graph admits a crossing-free drawing; a plane graph is a graph together with a particular such embedding. Edges may curve, and a crossing without a vertex is forbidden. A face is a connected region of the plane after the drawing is removed. Include the unbounded outside region. A bridge has the same face on both sides, so a facial boundary is naturally a closed walk that can repeat an edge rather than necessarily a simple cycle.

For a finite connected plane graph with nn vertices, ee edges, and ff faces, Euler's formula is n−e+f=2n-e+f=2. A tree has one face and e=n−1e=n-1, providing the base case. If an edge lies on a cycle, its two sides meet different faces; deleting that edge preserves connectedness and merges those faces. Both e and f decrease by one, leaving the expression unchanged. Continue until a spanning tree remains to prove the formula.

n−e+f=2(connected),n−e+f=1+c(c components)n-e+f=2\quad\text{(connected)},\qquad n-e+f=1+c\quad\text{(}c\text{ components)}
The unbounded face is included. The disconnected extension follows by adding c−1 connecting edges without creating faces.↔ Scroll wide equations horizontally.

Double-count boundary sides

Every embedded edge contributes two sides to facial boundary walks, even if both sides belong to one face. Hence the sum of face-boundary lengths equals 2e2e. In a connected simple plane graph with n≥3n\ge3, every facial boundary has length at least three. Combining 3f≤2e3f\le2e with Euler's formula gives e≤3n−6e\le3n-6. The simplicity and size hypotheses matter: parallel edges can enclose a two-sided face, and the two-vertex single-edge graph does not satisfy the displayed bound.

If the connected simple graph is also triangle-free and has at least three vertices, every facial boundary has length at least four, giving e≤2n−4e\le2n-4. Bridges do not invalidate the side count; a tree's sole facial walk traverses each edge twice and has length at least four under this size assumption. A bipartite graph has no odd cycle and therefore no triangle, so it satisfies the stronger bound whenever it is planar. These are necessary conditions, not general planarity tests.

∑Fℓ(F)=2e,e≤3n−6,e≤2n−4 if triangle-free\sum_{F}\ell(F)=2e,\qquad e\le3n-6,\qquad e\le2n-4\text{ if triangle-free}
The two inequalities assume a finite connected simple plane graph with n≥3; boundary walks count both sides of a bridge.↔ Scroll wide equations horizontally.

Obstructions and the limits of counting

The complete graph on five vertices has ten edges, exceeding the planar bound of nine. The complete bipartite graph with three vertices in each class has six vertices and nine edges; its triangle-free planar bound would allow at most eight. These contradictions prove nonplanarity without inspecting particular drawings. However, subdividing edges can increase the number of vertices enough to make the crude inequalities pass while leaving the essential obstruction intact. Passing the counts therefore does not establish a planar embedding.

Subdividing an edge replaces it by a path with new degree-two internal vertices. A crossing-free drawing of a subdivision could be smoothed along those paths to recover one of the original graph, so a subdivision of a nonplanar graph remains nonplanar. This explains why structural planarity theorems look for patterns beyond total edge counts. For a positive result, a clear crossing-free embedding is already a certificate. For a negative result, an impossible Euler count or a rigorously identified obstruction can provide one.

Work it through

Rule out three-by-three complete bipartite connectivity

Show that K3,3K_{3,3} is nonplanar. Count vertices and edges, choose the correct planar bound, and explain why the weaker bound alone is inconclusive.

  1. There are three vertices in each of two classes, hence six vertices. Every left vertex joins all three right vertices, giving nine distinct edges.

  2. The graph is simple, connected, and bipartite, so it is triangle-free. A planar embedding would therefore force e≤2n−4=8, contradicting the actual nine edges.

  3. The weaker simple planar bound gives e≤3n−6=12, which nine does satisfy. That is only a necessary condition and misses this obstruction. Using the bipartite structure is what sharpens the count enough to prove the claim.

The result

No planar embedding of K₃,₃ exists because its nine edges violate the triangle-free planar bound of eight.

The living notebook

Explore the model

Interactive lab

Interactive lab · modular

A cycle separates inside and outside

Pause and Reset, then set m = 6 and a = 1. Step through the whole orbit and ignore arrows: the displayed polygon is a six-cycle with n = e = 6 and two faces, including outside. Reset and set both m = 5 and a = 1; predict Euler's count remains two. This particular polygon illustrates an embedding; it is not a planarity detector for arbitrary edge sets.

A cycle separates inside and outsideAddition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Current readings: Residue r0: 0; Orbit period · m/gcd(m,a): 12; Distinct residues visited: 1 of 12. All parameters are adjustable with the labeled controls below.Repeated addition modulo 12: the current residue is 0, and the orbit period is 12.01234567891011+ 5mod 12An additive orbitn = 0rₙ = 0Period = 12Cycle starts at 0:0 → 5 → 10 → 3 →8 → 1 → 6 → 11 →4 → 9 → 2 → 7 → 0Exact residues · two additions per second
Additive orbitCurrent residue / next edge
Residue r0
0
Orbit period · m/gcd(m,a)
12
Distinct residues visited
1 of 12
t = 0 s

Addition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forThe outside face is essential: a plane cycle has two faces regardless of its number of vertices.

Pause & reason

Check your understanding

A connected simple triangle-free graph has eight vertices and fourteen edges. What follows?

Your turn

Try it yourself

The cube graph has eight vertices, twelve edges, and a standard crossing-free drawing. Compute its number of faces, then check the face-side count if every face boundary is a four-cycle. Explain what the counts do and do not prove.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Use connected Euler first. Count four sides per face and compare with two sides per edge.

Compare with the solution

Euler gives f=2−8+12=6 faces, including the unbounded one. Six four-sided boundaries contribute twenty-four edge sides, equal to twice the twelve edges. The graph also attains the triangle-free planar bound twelve=2×8−4. These counts are consistent with the supplied crossing-free drawing, which certifies planarity. Without that embedding or another positive argument, merely satisfying the numerical bounds would not itself prove planarity for an arbitrary graph with the same counts.

Keep the idea

Take it with you

  • Planarity means some crossing-free embedding exists; one crossed drawing proves little.
  • Euler's formula counts the unbounded face and adjusts for components.
  • Planar edge bounds can disprove planarity, but passing them is not sufficient.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.