Consequences of Euler's Formula

How many friendship connections can a group of people have? This is possible only if every friendship can be drawn without crossing lines. This innocent question forces a hard numerical ceiling on the size of any planar graph. That ceiling is the engine behind some of the most quotable facts in graph theory. From a single counting identity — Euler's formula $v - e + f = 2$ — one can derive several results. With almost no extra machinery, it yields an explicit bound on the number of edges a planar graph can have. It also gives a clean proof that the two smallest "obstructions" to planarity ( $K_5$ and $K_{3,3}$ ) are genuinely non-planar. Finally, it makes a serious dent in the proof of the Five Color Theorem. The reason this matters is that planarity is a global topological property. It asks whether an entire drawing avoids crossings. Euler's formula, by contrast, is a counting statement about vertices, edges, and faces. Turning a topological question into an arithmetic inequality is one of the great moves in combinatorics. It replaces "try to draw it and see" with "count and compare." This is also the historical seed of algebraic topology. Euler's formula is really the Euler characteristic of the sphere in disguise. The big picture is a chain of implications. Euler's formula, valid for any connected plane graph, combines with a simple fact about face degrees. Together they produce the edge bound $e \le 3v-6$ for simple planar graphs with at least three vertices. Sharpening the face-degree argument for triangle-free graphs gives the stronger bound $e \le 2v - 4$ . These two inequalities alone are enough to certify that $K_5$ and $K_{3,3}$ cannot be drawn in the plane without crossings. These are the first two non-planar graphs anyone meets. They are also, as will be foreshadowed, the two fundamental obstructions in Kuratowski's Theorem. The same edge bound also underlies a short proof that every planar graph has a vertex of degree at most 5. This fact is the combinatorial heart of the Five Color Theorem. This article develops that chain of reasoning fully. It proves the edge bound and the refined bound for bipartite/triangle-free graphs. It uses both to establish nonplanarity of $K_5$ and $K_{3,3}$ from scratch. It also sketches the reduction from small maximum degree to five-colorability. Along the way it flags exactly where each hypothesis (connectedness, simplicity, $v \ge 3$ ) is load-bearing. Dropping any one of them breaks the numerology.

Key takeaways

Euler's formula $v - e + f = 2$ for connected plane graphs yields the universal bound $e \le 3v - 6$ for simple planar graphs with $v \ge 3$ .
If the graph is triangle-free (no 3-cycles, e.g. bipartite), the bound sharpens to $e \le 2v - 4$ .
These two inequalities are pure arithmetic tests: compute $v$ and $e$ , compare to the bound, and nonplanarity follows instantly for $K_5$ ( $e = 10 > 3(5)-6=9$ ) and $K_{3,3}$ ( $e=9 > 2(6)-4=8$ ).
The edge bound forces some vertex of any simple planar graph to have degree $\le 5$ , by a counting (double-counting/pigeonhole) argument on the handshake sum.
This "min-degree $\le 5$ " fact is the combinatorial engine of the Five Color Theorem, proved by induction on vertices after deleting a low-degree vertex.
$K_5$ and $K_{3,3}$ are exactly the two graphs Kuratowski's Theorem later crowns as the universal obstructions to planarity.
Key idea: turning the topological question "can this be drawn without crossings?" into the arithmetic question "does $e$ exceed $3v-6$ (or $2v-4$ )?" converts geometry into counting.

Where this lives today

The edge bound $e \le 3v-6$ is the standard first-line test for planarity in algorithm design: before running an $O(v)$ planarity-testing algorithm (such as the Hopcroft–Tarjan algorithm), software can instantly reject a graph if it fails this arithmetic check, which costs only $O(1)$ time given $v$ and $e$ . In VLSI circuit design and printed-circuit-board layout, planarity of a connection graph determines whether a design can be realized without crossing wires on a single layer, and the edge-count test is the cheapest filter applied before expensive routing algorithms run. The corollary that every planar graph has a vertex of degree $\le 5$ is the combinatorial backbone of the Five Color Theorem: one deletes a low-degree vertex, colors the smaller graph by induction, then reinserts the vertex and (using a Kempe-chain argument when its neighbors already use 5 distinct colors) recolors to free up a color for it. This is a genuinely inductive proof technique — strong induction on the number of vertices — made possible only because the edge bound guarantees the low-degree vertex exists at every stage. The stronger Four Color Theorem (every planar map is 4-colorable) needed a much deeper case analysis, famously resolved with computer assistance by Appel and Haken in 1976, but its base combinatorial lemma about vertex degrees traces back to exactly this Euler-formula counting. In chemistry and materials science, fullerene molecules (carbon cages such as $C_{60}$ , buckminsterfullerene) are modeled as planar cubic graphs whose faces are pentagons and hexagons; Euler's formula forces exactly 12 pentagonal faces in any such structure, a striking chemical prediction extracted from pure counting. In network design, the edge bound explains why "mesh"-like planar network topologies cannot scale edge density arbitrarily, informing bounds on redundancy in circuit layouts and geographic information systems. In statistics and data visualization, planarity bounds inform when a graph drawing (e.g., of a social network or a Bayesian network's moralized graph) can in principle be rendered without edge crossings, which is a standard readability criterion in graph-drawing software.

Ask the tutor: How does the Kempe-chain recoloring step work when a degree-5 vertex's neighbors already use all five colors?

G = (V,E)

Intuition

Picture a planar drawing as a map: countries (faces) tiled edge-to-edge, meeting along borders (edges) and at corners (vertices). Euler's formula says the count of countries, borders, and corners is rigidly linked: $v - e + \phi = 2$ , no matter how the map is drawn, as long as it is connected. This is already surprising — the combinatorics of the tiling is fixed even though the geometry (shapes, sizes) can vary wildly. The extra idea that unlocks everything else is a second, independent count: every face is bounded by at least 3 edge-sides (a face can't have degree 1 or 2 in a simple graph with no multi-edges, since a face of degree 2 would need a repeated edge and degree 1 a loop), and every edge borders exactly two face-sides (or the same face twice, if it's a bridge). Summing face degrees therefore double-counts edges:

\sum_{f} \deg(f) = 2e, \qquad \deg(f) \ge 3 \text{ for every face } f.

Combined with $3\phi \le \sum_f \deg(f) = 2e$ , i.e. $\phi \le \tfrac{2}{3}e$ , substituting into Euler's formula eliminates $\phi$ and leaves a pure inequality relating $v$ and $e$ . That is the entire mechanism: two ways to count face-boundary incidences, squeezed through one topological identity, produce an edge cap.

Figure

A plane embedding of

K_4

v=4

e=6

\phi=4

, matching

v-e+\phi=4-6+4=2

Theorem statements

G

G

G

G

K_5

K_5

K_{3,3}

K_{3,3}

\le 5

v \le 6

Worked examples

Example 1: The Petersen graph is non-planar (checking via the sharper bound fails, plain bound succeeds). The Petersen graph $P$ has $v = 10$ vertices, each of degree $3$ , so $e = \tfrac{1}{2}\sum \deg(u) = \tfrac{1}{2}(10 \cdot 3) = 15$ edges. Its girth is $5$ (its shortest cycles have length 5, not 3), so it is triangle-free. Let's test both bounds. Plain bound: $3v - 6 = 3(10) - 6 = 24$ . We have $e = 15 \le 24$ — no contradiction, so this test is inconclusive; the Petersen graph is not ruled out by the plain edge bound. Sharper (girth-4) bound derived above requires only triangle-freeness and gives $2v - 4 = 2(10)-4 = 16$ . We have $e = 15 \le 16$ — still no contradiction! The sharper bound as stated (for girth $\ge 4$ ) is also inconclusive. This is instructive: neither bound proves the Petersen graph non-planar, because its edge count is genuinely compatible with planarity under these two tests. (One can sharpen further using girth $5$ , replacing the constant $4$ in the face-degree bound with $5$ : every face would need degree $\ge 5$ , giving $5\phi \le 2e$ , so $\phi \le 6$ , and then Euler's formula $10 - 15 + \phi = 2$ forces $\phi = 7$ , contradicting $\phi \le 6$ .) This shows the girth- $g$ refinement $e \le \tfrac{g}{g-2}(v-2)$ is the right tool, and it does certify the Petersen graph non-planar, while the cruder triangle-free bound (built for girth $\ge 4$ , not $\ge 5$ ) is too weak here. The lesson: Euler-formula bounds are sharp exactly to the girth hypothesis you feed them, and using a hypothesis weaker than what actually holds (triangle-free instead of girth-5) can leave you short of a proof.

Example 2: Using the edge bound to certify planarity is impossible in general, and to compute a concrete embedding count. Consider $G = K_{4,4}$ minus a perfect matching (sometimes called the 3-cube-like bipartite graph, but let's just compute directly). Take parts $A = \{a_1,a_2,a_3,a_4\}$ and $B = \{b_1,b_2,b_3,b_4\}$ , and join $a_i$ to $b_j$ for all $i \ne j$ (so each vertex has degree $3$ , since it connects to all of the other part except its matched partner). Then $v = 8$ , and $e = \tfrac12 \sum \deg(u) = \tfrac12(8 \cdot 3) = 12$ . This graph is bipartite, hence triangle-free, so the sharper bound applies: $2v - 4 = 2(8) - 4 = 12$ . We get $e = 12 \le 12$ — the bound is met with equality, so no contradiction arises and $G$ is not ruled out by this test. Does this mean $G$ is planar? The theorem only gives a necessary condition for planarity (if planar, then $e \le 2v-4$ ); satisfying the inequality does not by itself prove planarity — that would be affirming the consequent. In fact this graph, known as the 3-cube graph $Q_3$ 's bipartite double structure (it is isomorphic to the cube graph $Q_3$ , the 1-skeleton of a cube), is planar: one can draw the cube's edges as a square inside a square connected corner-to-corner without crossings, and equality $e = 2v-4$ in the theorem corresponds exactly to a quadrangulation of the sphere — every face has degree exactly $4$ . Indeed for $Q_3$ , Euler's formula with $v=8, e=12$ forces $\phi = 2 - v + e = 2 - 8 + 12 = 6$ , and $6$ faces each of degree $4$ satisfies $\sum \deg(f) = 24 = 2e$ exactly, consistent with a genuine cube-shaped embedding (6 square faces, just like the geometric cube). This example shows both the power of the bound (instant necessary condition, computed in one line) and its limit (it cannot single-handedly prove planarity, only rule it out).

G

Scope, edge cases & common traps

Situation	What happens	Why
$v \le 2$	Bound $e \le 3v-6$ can be negative or vacuous	Theorem explicitly requires $v \ge 3$ ; e.g. $v=2$ gives $3v-6=0$ but a single edge has $e=1$
Multigraphs / loops	Bound fails	Face-degree lower bound of $3$ needs simplicity (see counterexample)
Disconnected graphs	Bound still holds	Apply the connected case to each component; total $e$ only decreases relative to a connected graph on the same $v$
Triangle-free but not bipartite (e.g. 5-cycle)	Sharper bound $e\le 2v-4$ still valid	Only girth $\ge 4$ is used, not bipartiteness itself
Girth $g \ge 3$ general	Bound generalizes to $e \le \frac{g}{g-2}(v-2)$	Same double-counting proof with $\deg(f)\ge g$
Bound satisfied but graph still non-planar (e.g. some subdivisions)	Necessary, not sufficient	Full characterization needs Kuratowski's Theorem

Common trapThe converse is not proved here — and is false as a naive statement

Satisfying $e \le 3v-6$ (or $e \le 2v-4$ for triangle-free graphs) is a necessary condition for planarity, never a sufficient one. It is a common error to conclude "the edge count is fine, so the graph is planar." The Petersen graph example above shows a graph can satisfy the weaker bound and still be non-planar; more strikingly, there exist graphs meeting $e \le 3v-6$ that fail to be planar for structural reasons invisible to a pure edge count (they contain a $K_5$ - or $K_{3,3}$ -subdivision without having enough raw edges to trip the inequality). The correct converse-type statement — that a graph is planar if and only if it contains no subdivision of $K_5$ or $K_{3,3}$ — is Kuratowski's Theorem, whose proof is substantially deeper than counting and is not established by the arguments here.

The mathematician behind it

Origins · 1 minLeonhard Euler and how this was discovered

Leonhard Euler

1707–1783 · Basel, St. Petersburg, Berlin

Euler was the most prolific mathematician in history, contributing foundational results across analysis, number theory, mechanics, and what would become graph theory and topology. His 1736 resolution of the Seven Bridges of Königsberg problem is usually cited as the founding act of graph theory, and his polyhedron formula $v - e + f = 2$ , first stated in correspondence around 1750 and published in 1758, is the seed from which the whole edge-counting apparatus of planar graph theory grows. Euler worked at the courts of Frederick the Great in Berlin and Catherine the Great in St. Petersburg, continuing to produce mathematics at an enormous rate even after losing most of his eyesight later in life.

History

- 1736 — Euler resolves the Seven Bridges of Königsberg problem, an early graph-theoretic argument.

- 1750 — Euler communicates the polyhedron relation

v - e + f = 2

to Christian Goldbach.

- 1758 — Euler publishes the formula and a proof sketch for convex polyhedra.

- 1852 — Francis Guthrie poses the Four Color Problem, later linked to the Five Color Theorem via these same edge bounds.

- 1930 — Kazimierz Kuratowski proves his forbidden-subgraph characterization of planarity, crowning

K_5

and

K_{3,3}

as the fundamental obstructions foreshadowed by the edge-bound corollaries above.

Does

e \le 3v - 6

prove a graph is planar?

No. The theorem states that planarity implies $e \le 3v-6$ for simple graphs with $v\ge 3$ ; it does not state the converse. A graph can satisfy the inequality and still fail to be planar, as the Petersen graph example shows relative to the weaker bounds. To prove planarity you need either an explicit crossing-free drawing, a planarity-testing algorithm, or — to prove nonplanarity in general — Kuratowski's Theorem, which characterizes planarity exactly via forbidden subdivisions of $K_5$ and $K_{3,3}$ . The edge bound is only a quick necessary test, useful for instant rejection, not a full test.

Why does the bound change from

3v-6

2v-4

for triangle-free graphs?

Both bounds come from the same double-counting argument $\sum_f \deg(f) = 2e$ combined with a lower bound on face degree. For general simple planar graphs, faces have degree at least $3$ (the shortest possible cycle length), giving $3\phi \le 2e$ . If the graph is triangle-free, no face can be bounded by a 3-cycle, so every face has degree at least $4$ , giving the stronger inequality $4\phi \le 2e$ . Substituting the stronger face-degree floor into Euler's formula produces the sharper edge cap $e \le 2v-4$ . The general pattern, for girth $g$ , is $e \le \frac{g}{g-2}(v-2)$ .

Why must

v \ge 3

in the edge bound theorem?

The proof derives $e \le 3v-6$ algebraically from $\phi \le \tfrac{2}{3}e$ and Euler's formula, and this derivation is only meaningful once the graph actually has a cycle-capable structure or the tree case is checked directly. For $v=1$ , the bound gives $3(1)-6 = -3$ , an impossible (negative) upper bound for a nonnegative edge count, so the inequality is false for the single-vertex graph with $e=0$ edges (since $0 \not\le -3$ ). For $v=2$ , $3(2)-6=0$ , but a single edge already has $e=1 > 0$ . These small cases are genuine exceptions, not proof gaps, which is why the theorem's hypothesis explicitly restricts to $v \ge 3$ .

How exactly does the edge bound imply the Five Color Theorem?

The edge bound implies every simple planar graph has a vertex of degree $\le 5$ (proved above via the handshake lemma). The Five Color Theorem is then proved by strong induction on $v$ : remove a vertex $u$ of degree $\le 5$ , 5-color the remaining graph by the inductive hypothesis, then reinsert $u$ . If $u$ 's neighbors use at most 4 distinct colors among them, give $u$ the missing color. If $u$ has exactly 5 neighbors using all 5 colors, a Kempe-chain swapping argument on two color classes frees up a color for $u$ without recoloring the rest of the graph. The existence of the low-degree vertex at every inductive step is exactly what the edge bound guarantees.

Are

K_5

and

K_{3,3}

the only non-planar graphs?

No — there are infinitely many non-planar graphs, but $K_5$ and $K_{3,3}$ are special because every non-planar graph contains a subdivision (edges replaced by paths) of one of these two as a subgraph. This is the content of Kuratowski's Theorem, proved by Kuratowski in 1930 (and independently, in a related form using minors, by Wagner). The edge-count arguments in this article prove $K_5$ and $K_{3,3}$ themselves are non-planar, which is the easy half of the picture; showing they are the only essential obstructions requires substantially more machinery than counting alone.

Can the edge bound be used for graphs drawn on other surfaces, like a torus?

Yes, with a modified Euler characteristic. For a connected graph embedded on a surface of Euler characteristic $\chi$ (the sphere/plane has $\chi=2$ , the torus has $\chi=0$ ), the same double-counting argument gives $v - e + \phi = \chi$ and hence $e \le 3v - 3\chi$ for simple graphs with all faces of degree $\ge 3$ . On the torus ( $\chi = 0$ ) this gives $e \le 3v$ , which is why $K_7$ (with $v=7$ , $e=21=3v$ ) exactly saturates the torus bound and indeed embeds on the torus without crossings, unlike on the plane.

Does the theorem require the graph to be connected?

The clean statement of Euler's formula, $v-e+\phi=2$ , is for connected plane graphs. If $G$ is disconnected with $c$ components, the correct identity is $v - e + \phi = 1 + c$ . One can either apply the edge-bound proof to each component separately (each component individually satisfies $e_i \le 3v_i - 6$ once $v_i \ge 3$ , or trivially small components satisfy it too) and sum, or note that adding edges to connect the components only increases $e$ while keeping $v$ fixed, so if the connected version of the graph satisfies the bound, the original disconnected graph — having no more edges — satisfies it too.