Planar Graphs

Euler's polyhedral formula $V - E + F = 2$, the bound $E \leq 3V - 6$, non-planarity of $K_5$ and $K_{3,3}$, Kuratowski's theorem, and dual graphs.

Folio Official

March 1, 2026

1 Definition of Planar Graphs

Definition 1 (Planar graph).

A graph

G = (V, E)

is planar if it can be drawn in the plane

R^{2}

without any edge crossings. Such a crossing-free drawing is called a plane drawing (or embedding), and a graph equipped with a particular plane drawing is called a plane graph.

Example 2.

The complete graph

K_{4}

is planar: unfold one face of a tetrahedron to obtain a crossing-free drawing. That

K_{5}

is not planar will be proved below.

2 Faces and Euler's Formula

Definition 3 (Face).

In a plane drawing of a graph

G

, removing all vertices and edges from the plane leaves a collection of connected regions. Each such region is called a face. The unbounded region is called the outer face (or unbounded face). We write

F

for the number of faces.

Example 4.

A plane drawing of

K_{4}

has three triangular faces and one outer face, giving

F = 4

. With

V = 4

and

E = 6

, we get

V - E + F = 4 - 6 + 4 = 2

Theorem 5 (Euler's formula).

Let

G

be a connected plane graph with

V

vertices,

E

edges, and

F

faces. Then

V - E + F = 2.

Proof.

We induct on the number of edges

E

Base case. If

E = 0

, connectivity forces

G

to be a single vertex:

V = 1

and

F = 1

(only the outer face). Hence

V - E + F = 1 - 0 + 1 = 2

Inductive step. Suppose

E \geq 1

and the formula holds for all connected plane graphs with fewer than

E

edges. Pick an edge

e

Case 1:

e

is a bridge. Removing

e

splits

G

into two connected components

G_{1}

and

G_{2}

, and the two faces incident to

e

merge into one. By induction,

V_{i} - E_{i} + F_{i} = 2

for

i = 1, 2

. Since

V = V_{1} + V_{2}

E = E_{1} + E_{2} + 1

, and

F = F_{1} + F_{2} - 1

, we compute

V - E + F = (V_{1} + V_{2}) - (E_{1} + E_{2} + 1) + (F_{1} + F_{2} - 1) = 2 + 2 - 2 = 2

Case 2:

e

is not a bridge. Then

e

lies on a cycle, and removing

e

leaves

G

connected while merging the two faces on either side of

e

into one. So

V^{'} = V

E^{'} = E - 1

, and

F^{'} = F - 1

. By induction,

V - (E - 1) + (F - 1) = 2

, giving

V - E + F = 2

. □

Remark 6.

Euler originally discovered this formula for convex polyhedra (1752). Since the vertices, edges, and faces of a convex polyhedron correspond to those of a planar graph, the polyhedral formula

V - E + F = 2

is a special case of the graph-theoretic one.

3 Upper Bounds on the Number of Edges

Theorem 7 (

E \leq 3 V - 6

In a simple connected plane graph with

V \geq 3

, we have

E \leq 3 V - 6

Proof.

Each face is bounded by at least

3

edges (since the graph is simple, there are no loops or multiple edges). Each edge borders exactly

2

faces. Writing

S

for the sum of face sizes, we have

S \geq 3 F

and

S = 2 E

, so

2 E \geq 3 F

, i.e.,

F \leq 2 E /3

. Substituting into Euler's formula

F = 2 - V + E

gives

2 - V + E \leq \frac{2 E}{3},

which rearranges to

E \leq 3 V - 6

. □

Theorem 8 (Triangle-free bound).

In a simple connected plane graph with

V \geq 3

and no triangles (cycles of length

3

), we have

E \leq 2 V - 4

Proof.

Without triangles, each face is bounded by at least

4

edges. From

S \geq 4 F

and

S = 2 E

, we get

F \leq E /2

. Euler's formula then yields

2 - V + E \leq E /2

, i.e.,

E \leq 2 V - 4

. □

4 Non-Planarity of $K_{5}$ and $K_{3, 3}$

Theorem 9.

K_{5}

is not planar.

Proof.

K_{5}

has

V = 5

and

E = (2 5) = 10

. If it were planar, the inequality

E \leq 3 V - 6 = 9

would hold. Since

10 > 9

, this is a contradiction. □

$K_{5}$ :

Theorem 10.

K_{3, 3}

is not planar.

Proof.

K_{3, 3}

has

V = 6

and

E = 9

. Being bipartite,

K_{3, 3}

has no odd cycles and in particular no triangles. If it were planar, we would need

E \leq 2 V - 4 = 8

. Since

9 > 8

, this is a contradiction. □

$K_{3, 3}$ :

5 Kuratowski's Theorem

Definition 11 (Subdivision).

A subdivision of a graph

H

is a graph obtained by replacing edges of

H

with internally vertex-disjoint paths. That is, each edge

{u, v}

may be replaced by a new vertex

w

and two edges

{u, w}

and

{w, v}

; this operation may be applied finitely many times.

Theorem 12 (Kuratowski's theorem (1930)).

A graph

G

is planar if and only if it contains no subdivision of

K_{5}

K_{3, 3}

as a subgraph.

Remark 13.

Necessity is straightforward: subgraphs of planar graphs are planar, and subdivisions preserve planarity, yet

K_{5}

and

K_{3, 3}

are not planar. The proof of sufficiency is lengthy and is omitted here.

6 Dual Graphs

Definition 14 (Dual graph).

Given a connected plane graph

G

, the dual graph

G^{*}

is defined as follows:

The vertices of $G^{*}$ correspond to the faces of $G$ .
For each edge $e$ of $G$ , place an edge $e^{*}$ in $G^{*}$ connecting the two vertices that correspond to the faces on either side of $e$ .

Theorem 15.

For a connected plane graph

G

, we have

(G^{*})^{*} ≅ G

(a natural isomorphism).

Remark 16.

In the dual, cuts of

G

correspond to cycles of

G^{*}

, and vice versa. This duality plays a fundamental role in network theory and matroid theory.

Graph Theory Discrete Mathematics Textbook Planar Graphs Euler's Formula Kuratowski's Theorem

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Planar Graphs

Euler's polyhedral formula $V - E + F = 2$, the bound $E \leq 3V - 6$, non-planarity of $K_5$ and $K_{3,3}$, Kuratowski's theorem, and dual graphs.

Folio Official

March 1, 2026

1 Definition of Planar Graphs

Definition 1 (Planar graph).

A graph

G = (V, E)

is planar if it can be drawn in the plane

R^{2}

without any edge crossings. Such a crossing-free drawing is called a plane drawing (or embedding), and a graph equipped with a particular plane drawing is called a plane graph.

Example 2.

The complete graph

K_{4}

is planar: unfold one face of a tetrahedron to obtain a crossing-free drawing. That

K_{5}

is not planar will be proved below.

2 Faces and Euler's Formula

Definition 3 (Face).

In a plane drawing of a graph

G

F

for the number of faces.

Example 4.

A plane drawing of

K_{4}

has three triangular faces and one outer face, giving

F = 4

. With

V = 4

and

E = 6

, we get

V - E + F = 4 - 6 + 4 = 2

Theorem 5 (Euler's formula).

Let

G

be a connected plane graph with

V

vertices,

E

edges, and

F

faces. Then

V - E + F = 2.

Proof.

We induct on the number of edges

E

Base case. If

E = 0

, connectivity forces

G

to be a single vertex:

V = 1

and

F = 1

(only the outer face). Hence

V - E + F = 1 - 0 + 1 = 2

Inductive step. Suppose

E \geq 1

and the formula holds for all connected plane graphs with fewer than

E

edges. Pick an edge

e

Case 1:

e

is a bridge. Removing

e

splits

G

into two connected components

G_{1}

and

G_{2}

, and the two faces incident to

e

merge into one. By induction,

V_{i} - E_{i} + F_{i} = 2

for

i = 1, 2

. Since

V = V_{1} + V_{2}

E = E_{1} + E_{2} + 1

, and

F = F_{1} + F_{2} - 1

, we compute

V - E + F = (V_{1} + V_{2}) - (E_{1} + E_{2} + 1) + (F_{1} + F_{2} - 1) = 2 + 2 - 2 = 2

Case 2:

e

is not a bridge. Then

e

lies on a cycle, and removing

e

leaves

G

connected while merging the two faces on either side of

e

into one. So

V^{'} = V

E^{'} = E - 1

, and

F^{'} = F - 1

. By induction,

V - (E - 1) + (F - 1) = 2

, giving

V - E + F = 2

. □

Remark 6.

Euler originally discovered this formula for convex polyhedra (1752). Since the vertices, edges, and faces of a convex polyhedron correspond to those of a planar graph, the polyhedral formula

V - E + F = 2

is a special case of the graph-theoretic one.

3 Upper Bounds on the Number of Edges

Theorem 7 (

E \leq 3 V - 6

In a simple connected plane graph with

V \geq 3

, we have

E \leq 3 V - 6

Proof.

Each face is bounded by at least

3

edges (since the graph is simple, there are no loops or multiple edges). Each edge borders exactly

2

faces. Writing

S

for the sum of face sizes, we have

S \geq 3 F

and

S = 2 E

, so

2 E \geq 3 F

, i.e.,

F \leq 2 E /3

. Substituting into Euler's formula

F = 2 - V + E

gives

2 - V + E \leq \frac{2 E}{3},

which rearranges to

E \leq 3 V - 6

. □

Theorem 8 (Triangle-free bound).

In a simple connected plane graph with

V \geq 3

and no triangles (cycles of length

3

), we have

E \leq 2 V - 4

Proof.

Without triangles, each face is bounded by at least

4

edges. From

S \geq 4 F

and

S = 2 E

, we get

F \leq E /2

. Euler's formula then yields

2 - V + E \leq E /2

, i.e.,

E \leq 2 V - 4

. □

4 Non-Planarity of $K_{5}$ and $K_{3, 3}$

Theorem 9.

K_{5}

is not planar.

Proof.

K_{5}

has

V = 5

and

E = (2 5) = 10

. If it were planar, the inequality

E \leq 3 V - 6 = 9

would hold. Since

10 > 9

, this is a contradiction. □

$K_{5}$ :

Theorem 10.

K_{3, 3}

is not planar.

Proof.

K_{3, 3}

has

V = 6

and

E = 9

. Being bipartite,

K_{3, 3}

has no odd cycles and in particular no triangles. If it were planar, we would need

E \leq 2 V - 4 = 8

. Since

9 > 8

, this is a contradiction. □

$K_{3, 3}$ :

5 Kuratowski's Theorem

Definition 11 (Subdivision).

A subdivision of a graph

H

is a graph obtained by replacing edges of

H

with internally vertex-disjoint paths. That is, each edge

{u, v}

may be replaced by a new vertex

w

and two edges

{u, w}

and

{w, v}

; this operation may be applied finitely many times.

Theorem 12 (Kuratowski's theorem (1930)).

A graph

G

is planar if and only if it contains no subdivision of

K_{5}

K_{3, 3}

as a subgraph.

Remark 13.

Necessity is straightforward: subgraphs of planar graphs are planar, and subdivisions preserve planarity, yet

K_{5}

and

K_{3, 3}

are not planar. The proof of sufficiency is lengthy and is omitted here.

6 Dual Graphs

Definition 14 (Dual graph).

Given a connected plane graph

G

, the dual graph

G^{*}

is defined as follows:

The vertices of $G^{*}$ correspond to the faces of $G$ .
For each edge $e$ of $G$ , place an edge $e^{*}$ in $G^{*}$ connecting the two vertices that correspond to the faces on either side of $e$ .

Theorem 15.

For a connected plane graph

G

, we have

(G^{*})^{*} ≅ G

(a natural isomorphism).

Remark 16.

In the dual, cuts of

G

correspond to cycles of

G^{*}

, and vice versa. This duality plays a fundamental role in network theory and matroid theory.

Graph Theory Discrete Mathematics Textbook Planar Graphs Euler's Formula Kuratowski's Theorem

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Planar Graphs

1 Definition of Planar Graphs

2 Faces and Euler's Formula

3 Upper Bounds on the Number of Edges

4 Non-Planarity of $K_{5}$ and $K_{3, 3}$

5 Kuratowski's Theorem

6 Dual Graphs

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

Planar Graphs

1 Definition of Planar Graphs

2 Faces and Euler's Formula

3 Upper Bounds on the Number of Edges

4 Non-Planarity of $K_{5}$ and $K_{3, 3}$

5 Kuratowski's Theorem

6 Dual Graphs

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

1 Definition of Planar Graphs

2 Faces and Euler's Formula

3 Upper Bounds on the Number of Edges

4 Non-Planarity ofK5​andK3,3​

5 Kuratowski's Theorem

6 Dual Graphs

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

1 Definition of Planar Graphs

2 Faces and Euler's Formula

3 Upper Bounds on the Number of Edges

4 Non-Planarity ofK5​andK3,3​

5 Kuratowski's Theorem

6 Dual Graphs

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

4 Non-Planarity of $K_{5}$ and $K_{3, 3}$

4 Non-Planarity of $K_{5}$ and $K_{3, 3}$