Planar Graphs and Euler's Formula

Can every graph be drawn on paper so that its edges never cross? This simple question is easy to ask a child. Yet it turns out to organize an enormous amount of combinatorics, topology, and computer science. Some graphs — a triangle, a cycle, a tree — obviously admit such a drawing. Others, like the "utility graph" connecting three houses to three utilities, stubbornly resist every attempt. No matter how cleverly you route the edges, crossings remain unavoidable. Planar graphs, the graphs that can be drawn without crossings, form one of the most beautifully constrained classes in all of graph theory. The reason planarity matters so much is that a planar drawing is not just a picture. It is combinatorial data. Once a graph is embedded in the plane, it carves the plane into regions called faces. These faces interact with the vertices and edges through an astonishingly rigid numerical law: Euler's formula, v−e+f=2v - e + f = 2. This single equation was discovered by Euler in the context of polyhedra. It is the seed from which an entire structure theory of planar graphs grows: bounds on the number of edges, forced low-degree vertices, the impossibility of certain subgraphs, and ultimately a full characterization (Kuratowski's theorem) of which graphs are planar at all. The big picture is that planarity is a global topological constraint with local combinatorial consequences. Euler's formula converts a statement about embeddability into an algebraic identity relating three counts. That identity can be manipulated with elementary inequalities to derive surprising facts. These facts seem to have nothing to do with topology. For instance, every planar graph has a vertex of degree at most 5. Also, K5K_5 cannot be drawn in the plane without crossings. This article builds the formal machinery of plane embeddings and faces. It proves Euler's formula rigorously by induction on edges, and then extracts its standard consequences. It assumes familiarity with Connectivity and Components and Graph Coloring and Chromatic Number. It also sets up the tools needed for Kuratowski's Theorem and the broader family of Consequences of Euler's Formula.

Key takeaways
  • A graph is planar if it can be drawn in the plane with no edge crossings; such a drawing is a plane embedding.
  • A plane embedding divides the plane into connected regions called faces, including one unbounded outer face.
  • Euler's formula: for a connected plane graph, v−e+f=2v - e + f = 2, where v,e,fv,e,f count vertices, edges, faces.
  • The formula is proved by induction on the number of edges, using spanning trees as the base case.
  • Counting edge-face incidences yields e≤3v−6e \le 3v - 6 for simple planar graphs with v≥3v \ge 3, hence every planar graph has a vertex of degree ≤5\le 5.
  • These bounds show K5K_5 and K3,3K_{3,3} are non-planar, foreshadowing Kuratowski's Theorem.
  • Key idea: planarity is a topological property, but Euler's formula turns it into a rigid algebraic constraint on vv, ee, and ff.

Where this lives today

Euler's formula and planarity are not museum pieces; they are load-bearing tools across mathematics and computing. In graph algorithms, planarity testing (linear-time algorithms exist, e.g. Hopcroft–Tarjan) and planar graph data structures exploit e≤3v−6e \le 3v-6 to guarantee sparse representations, which underlies efficient algorithms for shortest paths, network flow, and graph drawing in planar settings. In VLSI circuit design and printed circuit board layout, planarity corresponds to a circuit being routable on a single conducting layer without wires crossing, and Euler's formula bounds how many components and connections can fit. In cartography and GIS, planar subdivisions (maps of countries, states, districts) are literally plane graphs, and the four-color theorem — whose statement concerns exactly such maps — relies on the sparsity and low-degree consequences of Euler's formula (specifically the existence of a vertex of degree ≤5\le 5) as a key ingredient in every known proof, tying back directly to Graph Coloring and Chromatic Number. In topology, the formula generalizes to the Euler characteristic v−e+f=χv-e+f = \chi of surfaces, where χ=2\chi=2 for the sphere/plane, χ=0\chi=0 for the torus, and so on, giving a bridge from elementary combinatorics to algebraic topology. In chemistry and materials science, fullerene molecules (like buckminsterfullerene) are modeled by planar 3-regular graphs whose face structure is constrained by Euler's formula, forcing exactly twelve pentagonal faces regardless of how many hexagonal faces are present. And in network science, planarity constraints are used to model road networks and certain classes of physical infrastructure networks where crossing-free layout is a hard physical requirement.

Ask the tutor: How does the proof of Euler's formula change if we allow the graph to be embedded on a torus instead of the plane?

DefinitionPlanar graph, plane graph, and faces

Let G=(V,E)G = (V,E) be a finite simple graph (no loops or multiple edges, unless stated otherwise). A drawing of GG in the plane assigns to each vertex a distinct point of R2\mathbb{R}^2 and to each edge uvuv a simple arc (a homeomorphic image of [0,1][0,1]) joining the points for uu and vv, such that: 1. no arc passes through a vertex point other than its own two endpoints, and 2. distinct arcs intersect only, if at all, at common endpoints. GG is planar if it admits a drawing satisfying (1) and (2) — that is, a drawing with no edge crossings. A plane graph is a planar graph together with a fixed such drawing; the drawing itself is called a plane embedding of GG. Given a plane graph, the drawing removes from the plane a set of points (vertices and edge-arcs). The connected components of the remaining open set R2∖(drawing)\mathbb{R}^2 \setminus (\text{drawing}) are called the faces of the plane graph. Exactly one face is unbounded; it is called the outer face, and all others are inner (bounded) faces. The boundary of a face is the set of edges and vertices adjacent to it; a face is said to be incident to the vertices and edges on its boundary. Planarity is a property of the abstract graph GG (does some crossing-free drawing exist), while "face," "outer face," and the specific face structure are properties of a particular embedding — a planar graph may admit several combinatorially different embeddings (though for 3-connected planar graphs the face structure is in fact unique, a fact known as Whitney's theorem).

Intuition

Think of a plane graph as a map: vertices are cities, edges are roads, and faces are the countries the roads carve out of the plane, plus one infinite "ocean" surrounding everything. Euler's formula says that no matter how you draw the map — as long as it stays connected and crossing-free — the quantity v−e+fv - e + f is always exactly 22. Add a country by adding a road that splits a region in two, and you gain one face but also one edge, so the alternating sum doesn't change. Add a new city with a new road sticking off an existing structure (a "dead-end" road, a bridge), and you gain one vertex and one edge but no new face, again preserving the sum. Euler's formula is really a conservation law for a certain graph-building process. The second piece of intuition is a counting trick: each face is bounded by at least 3 edges (assuming at least 3 vertices and no multi-edges/loops), and each edge borders at most 2 faces. Summing "boundary length" two ways — once over faces, once over edges — turns 3f≤2e3f \le 2e into a linear inequality, and combining it with Euler's formula produces the sparsity bound e≤3v−6e \le 3v-6. This is why planar graphs are "sparse": they simply cannot have too many edges relative to vertices, which is exactly the obstruction that rules out dense graphs like K5K_5.

Figure
A plane embedding of a graph with v=4v=4, e=6e=6, f=4f=4, checking v−e+f=2v-e+f=2
v₁ v₂ v₃ v₄ f₁ f₂ f₃ f∞ (outer) v − e + f = 4 − 6 + 4 = 2 ✓
TheoremEuler's Formula for Connected Plane Graphs

Let GG be a connected plane graph with vv vertices, ee edges, and ff faces (including the outer face). Then

v−e+f=2.v - e + f = 2.
Proof

We induct on the number of edges e≥0e \ge 0. The proof technique is induction on ee, using the structural fact that a connected graph is a tree iff it has v−1v-1 edges and no cycles.

Base case. Suppose GG has no cycles. Since GG is connected, it is a tree, so e=v−1e = v - 1. A tree drawn in the plane has no closed curves made of edges, so its complement in the plane is a single connected unbounded region: f=1f = 1. (This is geometrically clear by induction on the tree's construction, adding one leaf at a time; a single point or single edge already has one face, the whole plane minus the drawing, and attaching a new leaf edge to an existing tree cannot separate the plane because a tree contains no cycle, hence no simple closed curve, and by the Jordan curve theorem only a simple closed curve can separate the plane into an inside and outside.) Then

v−e+f=v−(v−1)+1=2.v - e + f = v - (v-1) + 1 = 2.

This establishes the base case: the formula holds whenever GG is a tree.

Inductive step. Suppose GG is connected with e≥1e \ge 1 edges and the formula holds for every connected plane graph with fewer than ee edges. If GG is a tree, we are done by the base case above (trees with any number of edges are covered there). So suppose GG is not a tree; then GG contains a cycle, hence contains some edge ε\varepsilon lying on a cycle.

Claim: removing ε\varepsilon merges the two faces incident to it into one, decreasing the face count by exactly 11, while the vertex count is unchanged and the edge count decreases by 11. To justify the claim: since ε\varepsilon lies on a cycle CC, the arc for ε\varepsilon is part of a simple closed curve in the plane (formed by CC's edges). By the Jordan curve theorem, CC separates the plane into an inside and an outside, so the two sides of ε\varepsilon locally belong to two different faces of GG (a bridge could never do this, since removing a bridge from a connected graph disconnects it, but an edge on a cycle is never a bridge). Call these two faces F1F_1 and F2F_2; they are distinct because points immediately on either side of ε\varepsilon near an interior point of the arc cannot be connected by a path avoiding the drawing without crossing CC at some point (a consequence of the Jordan curve theorem separating the plane by CC). Deleting the arc for ε\varepsilon merges F1F_1 and F2F_2 into a single connected region, and does not affect any other face, since no other face touches ε\varepsilon. All other faces, edges, and vertices of GG are untouched by this deletion. Let G′=G−εG' = G - \varepsilon with the inherited plane drawing. Then G′G' is still connected: since ε\varepsilon was on a cycle, deleting it cannot disconnect GG (a cycle edge is never a cut edge — any path through ε\varepsilon can be rerouted around the rest of the cycle CC). We have

v(G′)=v(G),e(G′)=e(G)−1,f(G′)=f(G)−1,v(G') = v(G), \qquad e(G') = e(G) - 1, \qquad f(G') = f(G) - 1,

and G′G' is a connected plane graph with e−1e-1 edges, so the inductive hypothesis gives v(G′)−e(G′)+f(G′)=2v(G') - e(G') + f(G') = 2. Substituting,

v(G)−(e(G)−1)+(f(G)−1)=2⟹v(G)−e(G)+f(G)=2.v(G) - (e(G)-1) + (f(G)-1) = 2 \quad\Longrightarrow\quad v(G) - e(G) + f(G) = 2.

By induction, the formula v−e+f=2v - e + f = 2 holds for every connected plane graph. ■\blacksquare

∎
CorollaryEuler's formula for a plane graph with kk components

If GG is a plane graph with vv vertices, ee edges, ff faces, and kk connected components, then

v−e+f=1+k.v - e + f = 1 + k.
Proof

We use Euler's Formula for Connected Plane Graphs together with a merging argument, another instance of induction — this time on the number of components. If k=1k=1, this is exactly the theorem above. Suppose k≥2k \ge 2 and the claim holds for plane graphs with k−1k-1 components. Let GG have components G1,…,GkG_1,\dots,G_k, and let G−=G1∪⋯∪Gk−1G^- = G_1 \cup \cdots \cup G_{k-1} (a plane graph with k−1k-1 components, using the induced sub-drawing, which is still a valid plane drawing since deleting a subset of a valid drawing leaves a valid drawing). Since GkG_k is drawn inside some face FF of G−G^- (it lies in one connected region of the complement of G−G^-'s drawing, as GkG_k itself is connected and disjoint from G−G^-), attaching GkG_k back inside FF does not create new faces outside FF, and it replaces FF by exactly the faces of GkG_k's own drawing restricted to region FF, contributing f(Gk)f(G_k) faces in place of the single face FF (one of which absorbs the rest of FF as its own outer boundary). Formally,

f(G)=f(G−)+f(Gk)−1,f(G) = f(G^-) + f(G_k) - 1,

since FF is replaced by f(Gk)f(G_k) faces rather than counted separately. Also v(G)=v(G−)+v(Gk)v(G) = v(G^-)+v(G_k) and e(G)=e(G−)+e(Gk)e(G) = e(G^-)+e(G_k). By the inductive hypothesis, v(G−)−e(G−)+f(G−)=1+(k−1)=kv(G^-) - e(G^-) + f(G^-) = 1 + (k-1) = k, and by the theorem, v(Gk)−e(Gk)+f(Gk)=2v(G_k)-e(G_k)+f(G_k)=2. Adding these two equations and using the face relation above:

[v(G−)+v(Gk)]−[e(G−)+e(Gk)]+[f(G−)+f(Gk)]=k+2,[v(G^-)+v(G_k)] - [e(G^-)+e(G_k)] + [f(G^-)+f(G_k)] = k + 2,

and since f(G)=f(G−)+f(Gk)−1f(G) = f(G^-)+f(G_k) - 1, substituting gives

v(G)−e(G)+(f(G)+1)=k+2  ⟹  v(G)−e(G)+f(G)=k+1.v(G) - e(G) + (f(G)+1) = k+2 \implies v(G)-e(G)+f(G) = k+1.

This completes the induction. ■\blacksquare

∎
LemmaEdge bound for simple planar graphs

Let GG be a simple, connected planar graph with v≥3v \ge 3 vertices and ee edges. Then

e≤3v−6.e \le 3v - 6.

Moreover if GG is triangle-free (contains no 3-cycle) and v≥3v \ge 3, then e≤2v−4e \le 2v - 4.

Proof

Fix a plane embedding of GG with ff faces; by Euler's Formula for Connected Plane Graphs, v−e+f=2v-e+f=2. Since v≥3v \ge 3 and GG is simple (no loops, no multi-edges) and connected, every face boundary is a closed walk using at least 33 edges: a face cannot be bounded by fewer than 33 edge-sides, because a boundary of length 11 would require a loop and a boundary of length 22 would require either a multi-edge or a bridge counted twice bordering a single face on both sides — the latter is possible for bridges, but even then the total boundary length is what we bound, and the general inequality 3f≤2e3f \le 2e still holds via the following global count, which we now make precise. For each face ϕ\phi, let ℓ(ϕ)\ell(\phi) denote its boundary length: the number of edge-sides incident to it, where an edge that is a bridge (has the same face on both sides) contributes 22 to that single face's boundary length, and any other edge contributes 11 to each of the (at most two, possibly equal only for bridges) faces it borders. Every edge contributes exactly 22 to ∑ϕℓ(ϕ)\sum_\phi \ell(\phi) in total (once for each side), so

∑ϕℓ(ϕ)=2e.\sum_{\phi} \ell(\phi) = 2e.

Since GG is simple and connected with v≥3v\ge 3, every face has ℓ(ϕ)≥3\ell(\phi) \ge 3: a face boundary that used fewer than 3 edge-sides would force either a loop (ℓ=1\ell=1 around a single vertex, impossible as GG is simple) or a boundary consisting of two parallel edge-sides between the same two vertices with no third vertex anywhere, which since v≥3v \geq 3 and GG connected would force disconnection or a multi-edge, both excluded. Hence

2e=∑ϕℓ(ϕ)≥3f  ⟹  f≤23e.2e = \sum_\phi \ell(\phi) \ge 3f \implies f \le \tfrac{2}{3}e.

Substituting into Euler's formula f=2−v+ef = 2 - v + e:

2−v+e≤23e  ⟹  13e≤v−2  ⟹  e≤3v−6.2 - v + e \le \tfrac{2}{3}e \implies \tfrac{1}{3}e \le v - 2 \implies e \le 3v-6.

For the triangle-free case, no face can have ℓ(ϕ)=3\ell(\phi)=3 (a length-3 boundary using 33 distinct edges would trace a 3-cycle; a bridge cannot contribute to a length-3 face boundary alone without creating a repeated edge on a boundary of odd minimal length forcing an actual triangle or contradiction with simplicity, so under triangle-freeness every face has ℓ(ϕ)≥4\ell(\phi)\ge 4). Hence 2e=∑ϕℓ(ϕ)≥4f2e = \sum_\phi \ell(\phi) \ge 4f, so f≤e/2f \le e/2, and Euler's formula gives

2−v+e≤12e  ⟹  12e≤v−2  ⟹  e≤2v−4.■2 - v + e \le \tfrac12 e \implies \tfrac12 e \le v-2 \implies e \le 2v-4. \qquad \blacksquare
∎
CorollaryMinimum degree bound

Every simple planar graph GG with v≥3v \ge 3 vertices has a vertex of degree at most 55.

Proof

We may assume GG is connected; if not, apply the argument to a component with ≥3\ge 3 vertices (a component with fewer vertices has maximum possible degree ≤1\le 1 or ≤0\le 0, so the claim is trivial there), or note isolated small components have vertices of degree 00 or 1≤51 \le 5. Suppose toward contradiction every vertex has degree ≥6\ge 6. By the handshake lemma,

2e=∑u∈Vdeg⁡(u)≥6v  ⟹  e≥3v.2e = \sum_{u\in V} \deg(u) \ge 6v \implies e \ge 3v.

But by the Edge bound for simple planar graphs lemma, e≤3v−6<3ve \le 3v - 6 < 3v for all v≥3v\ge 3. This contradicts e≥3ve \ge 3v. Hence some vertex has degree ≤5\le 5. ■\blacksquare

∎

Worked examples

Example 1: verifying and using Euler's formula on an asymmetric graph. Let GG be the graph with vertex set {1,2,3,4,5}\{1,2,3,4,5\} and edge set

E={12, 13, 14, 23, 24, 34, 45}.E = \{12,\,13,\,14,\,23,\,24,\,34,\,45\}.

So vertices 1,2,3,41,2,3,4 form a complete graph K4K_4, and vertex 55 is attached only to vertex 44 by a single pendant edge. Here v=5v = 5 and e=7e = 7. GG is planar: draw K4K_4 as a triangle 1,2,31,2,3 with vertex 44 placed inside connected to all three (the standard planar drawing of K4K_4), and then attach the pendant vertex 55 by a short edge from 44 out into the outer face. This is a valid crossing-free drawing. Count the faces directly from this drawing. The planar K4K_4 alone has 44 faces: three inner triangular faces (124,134,234124, 134, 234, say — depending on which face vertex 44 is nested in, concretely the faces bounded by 11-22-44, 11-33-44, 22-33-44) and one outer face bounded by the outer triangle 11-22-33. Attaching the pendant edge 4545 inside the outer face does not split any face (a pendant edge, a bridge, borders the same face on both sides), so it contributes no new face. Hence

f=4.f = 4.

Check Euler's formula: v−e+f=5−7+4=2v - e + f = 5 - 7 + 4 = 2. ✓. Now use the edge bound as a sanity check: with v=5v=5, the lemma predicts e≤3(5)−6=9e \le 3(5)-6 = 9. Indeed e=7≤9e = 7 \le 9, consistent (and not tight, since GG is not a maximal planar triangulation — one could still add two more edges, namely 1515 and 2525 or 3535, wait: check feasibility — adding edge 1515 keeps it planar since 55 sits in the outer face near vertex 11; in fact a maximal planar graph on 55 vertices has exactly 3(5)−6=93(5)-6=9 edges, consistent with the bound being achievable). Finally, verify the minimum degree corollary: degrees are deg⁡(1)=3,deg⁡(2)=3,deg⁡(3)=3,deg⁡(4)=4,deg⁡(5)=1\deg(1)=3,\deg(2)=3,\deg(3)=3,\deg(4)=4,\deg(5)=1. The minimum is 1≤51 \le 5 (in fact here every vertex has degree ≤5\le 5, consistent with, and far from tight against, the corollary).

Example 2: using Euler's formula to compute an unknown face count, and to detect non-planarity via the bound. A connected planar map (plane graph) has v=12v = 12 vertices and every face is bounded by exactly 55 edges (a "planar pentagonal map", e.g. combinatorially like a dodecahedron graph), with each edge bordering exactly two distinct faces (no bridges). Find ee and ff. Since each face has boundary length 55 and each edge is counted twice across all face boundaries (once per side, and here no bridge double-counts a single face), we have

5f=2e.5f = 2e.

Euler's formula gives v−e+f=2v - e + f = 2, i.e. 12−e+f=212 - e + f = 2, so e=f+10e = f + 10. Substitute into 5f=2e=2(f+10)=2f+205f = 2e = 2(f+10) = 2f+20:

5f−2f=20  ⟹  3f=20  ⟹  f=203.5f - 2f = 20 \implies 3f = 20 \implies f = \tfrac{20}{3}.

This is not an integer, which is a contradiction. Conclusion: no such plane graph exists — there is no connected planar map on exactly 1212 vertices in which every face has boundary length exactly 55 with no bridges. (Contrast: the actual dodecahedral graph has v=20,e=30,f=12v=20, e=30, f=12, and indeed 5⋅12=60=2⋅305\cdot 12 = 60 = 2\cdot 30 and 20−30+12=220-30+12=2 checks out — the discrepancy above shows that v=12v=12 was simply an inconsistent choice of parameters, and this computation is exactly the kind of arithmetic feasibility check Euler's formula enables before ever attempting to draw a graph.) As a second use of the bound: suppose someone claims to have a simple planar graph with v=6v = 6 vertices and e=14e = 14 edges. The lemma requires e≤3v−6=12e \le 3v-6 = 12 for planarity. Since 14>1214 > 12, no such planar graph can exist — this instantly rules out planarity for something like K6K_6 (which has (62)=15\binom{6}{2}=15 edges, far exceeding 1212), without ever attempting to draw it or invoking Kuratowski's Theorem.

CounterexampleWhy connectivity is needed in Euler's formula

Drop the hypothesis that GG is connected, but keep the naive formula v−e+f=2v-e+f=2 (rather than the corrected v−e+f=1+kv-e+f=1+k). Let GG consist of two disjoint triangles drawn side by side in the plane, with no edges between them. Here v=6v = 6, e=6e = 6. Draw them as two separate triangular outlines. The faces are: the interior of the first triangle, the interior of the second triangle, and the single unbounded outer face surrounding both — note the outer face is shared by both components, since it is one connected unbounded region touching both triangles. So f=3f = 3. Compute: v−e+f=6−6+3=3≠2v - e + f = 6 - 6 + 3 = 3 \ne 2. The naive formula fails because GG has k=2k=2 components. The corrected version, v−e+f=1+kv-e+f = 1+k, gives 1+2=31+2=3, matching the count exactly. This shows the connectivity hypothesis in the basic theorem is not a technical nicety — omitting it changes the constant on the right-hand side, and using v−e+f=2v-e+f=2 for a disconnected plane graph gives a false equation.

Scope, edge cases & common traps

SituationWhat to watch for
Disconnected plane graphsUse v−e+f=1+kv-e+f=1+k, not v−e+f=2v-e+f=2
Multigraphs / loopsFace boundary lengths can be 11 (loop) or 22 (parallel edges); the e≤3v−6e\le 3v-6 bound assumes simplicity
Bridges (cut edges)A bridge borders the same face on both sides; it contributes 22 to that face's boundary length but only 11 edge
Different embeddings of the same GGFace count ff is still forced to satisfy Euler's formula (since it only depends on v,e,kv,e,k), but which sets of vertices/edges bound which face can differ, except for 3-connected planar graphs (Whitney's uniqueness theorem)
v<3v < 3The bound e≤3v−6e\le 3v-6 can be vacuous or wrong (e.g. v=1,e=0v=1,e=0 gives −3-3, meaningless as an edge bound); always check v≥3v\ge 3
Non-planar graphsEuler's formula simply does not apply; K5,K3,3K_5,K_{3,3} have no plane embedding at all, so ff is undefined for them

The mathematician behind it

Origins · 1 minLeonhard Euler and how this was discovered
LE
Leonhard Euler
1707–1783 · Imperial Russian Academy of Sciences, St. Petersburg / Berlin Academy

Euler was the most prolific mathematician in history, contributing foundational results across number theory, analysis, mechanics, and what would become graph theory. His 1736 resolution of the Königsberg bridge problem is widely regarded as the founding act of graph theory. His polyhedral formula, v−e+f=2v-e+f=2, first stated for convex polyhedra around 1750 (in letters to Christian Goldbach and in a paper presented to the St. Petersburg Academy), is the direct ancestor of the plane-graph version proved here, since the graph formed by a convex polyhedron's vertices and edges, projected onto a plane (or sphere), is always planar and connected.

History
- 1736 — Euler resolves the Seven Bridges of Königsberg problem, effectively initiating graph theory.
- 1750 — Euler communicates the polyhedral formula v−e+f=2v - e + f = 2 to Goldbach, for convex polyhedra.
- 1752–1753 — Euler publishes proofs and further development of the formula in the St. Petersburg Academy proceedings.
- 1847 — Cauchy and others rigorize and generalize the formula, connecting it to plane graph theory explicitly.
- 1930 — Kazimierz Kuratowski publishes the full topological characterization of planar graphs, building directly on the sparsity consequences of Euler's formula.
Does Euler's formula prove that a graph is planar?

No. Euler's formula is a consequence of having a plane embedding, not a criterion that grants one. It takes as given a graph already drawn without crossings and relates the resulting vertex, edge, and face counts. You cannot run the formula "backwards" to conclude planarity just because vv, ee satisfy some numeric relation; the edge bound e≤3v−6e \le 3v-6 derived from it is a necessary condition for planarity (its failure proves non-planarity), but it is not sufficient. There exist non-planar graphs satisfying e≤3v−6e \le 3v-6, so a full planarity characterization requires more machinery, namely Kuratowski's Theorem.

Does every planar graph have a unique face structure?

Not in general. A planar graph can have multiple combinatorially different plane embeddings with different face boundaries, especially if the graph has low connectivity (e.g., graphs with cut vertices can be "flipped" at those vertices to rearrange which pieces sit inside which face). However, Whitney's theorem states that every 3-connected planar graph has an essentially unique embedding on the sphere, meaning its face structure (the set of face boundaries) is the same in every plane embedding, up to the choice of outer face and reflection. Euler's formula's numeric conclusion, v−e+f=2v-e+f=2, holds for any embedding of a connected planar graph regardless of this uniqueness question, since ff is forced by vv and ee alone.

Why must every face have boundary length at least 3 in a simple graph?

A face boundary of length 11 would trace a closed walk using a single edge-side, which only happens with a loop (an edge from a vertex to itself) — excluded by simplicity. A face boundary of length 22 using two distinct edges between the same two vertices requires a multi-edge (two parallel edges enclosing a "bigon" face) — also excluded by simplicity, since simple graphs allow at most one edge between any two vertices. The only length-22 situation in a simple graph is a bridge bordering one face on both sides, but that face's total boundary length is still at least 33 once you account for the rest of its perimeter, provided the graph has v≥3v\ge 3 vertices, since a face cannot be bounded solely by a single back-and-forth edge with nothing else in a connected simple graph on 3+ vertices.

Can Euler's formula be used for graphs drawn on other surfaces, like a torus?

Yes, and this is one of the deepest generalizations of the idea. For a connected graph embedded on a closed orientable surface of genus gg (a sphere with gg handles), the analogous identity is v−e+f=2−2gv - e + f = 2 - 2g, where 2−2g2-2g is called the Euler characteristic of the surface. The plane (or equivalently the sphere, via stereographic projection) is the genus-00 case, recovering v−e+f=2v-e+f=2. This generalization lets you define and study "toroidal graphs" and other surface-embeddable graph classes using the same edge-counting techniques used here, replacing 22 by 2−2g2-2g throughout the derivation of bounds like e≤3v−6e\le 3v-6.

Is the outer face fundamentally different from the inner faces?

Topologically, no — on the sphere (via stereographic projection, which turns the plane's point at infinity into an ordinary point), the outer face is just another bounded face like any other, and "outer" is only meaningful once you fix a particular point (or face) to serve as the "point at infinity" for the planar drawing. In practice, when working directly in the plane, the outer face is the one unbounded region, and it must be included in the face count ff in Euler's formula — a common student error is to forget to count the outer face, which silently shifts every computed value of ff down by one and breaks the identity.

Does Euler's formula require the graph to be simple?

No — the theorem as proved here (via induction on edges, base case trees) works for connected multigraphs (graphs with loops and parallel edges) too, as long as "plane graph" is interpreted correctly (loops are drawn as simple closed curves, parallel edges as non-crossing arcs). What does require simplicity is the derived inequality e≤3v−6e \le 3v-6, since that argument used the fact that no face can have boundary length less than 33, which fails once loops (boundary length 11) or parallel edges (boundary length 22, forming a "bigon" face) are allowed.

How does Euler's formula connect to Kuratowski's theorem?

Euler's formula gives necessary numerical conditions for planarity (like e≤3v−6e\le 3v-6), which are enough to rule out specific dense graphs such as K5K_5 and K3,3K_{3,3} directly by arithmetic. But these numerical conditions are not sufficient — there exist graphs satisfying e≤3v−6e\le 3v-6 that are still non-planar. Kuratowski's Theorem closes this gap completely: it states that a graph is planar if and only if it contains no subgraph that is a subdivision of K5K_5 or K3,3K_{3,3}. Euler's formula is the essential first step used inside the proof of Kuratowski's theorem, precisely because it is what shows K5K_5 and K3,3K_{3,3} themselves must be forbidden.

Before this

Where this leads